\documentclass[12pt,a4paper]{article} \usepackage{german} \usepackage[latin1]{inputenc} \usepackage{fancyhdr} \usepackage{amstext,amssymb} \usepackage{graphicx} \pagestyle{fancy} \textwidth17cm \textheight23.7cm \headwidth17cm \topmargin-0.8cm \headheight12pt \headsep36pt \oddsidemargin-0.5cm \footskip1.5cm \parskip2ex \nonfrenchspacing \DeclareFontFamily{OT1}{mvs}{} \DeclareFontShape{OT1}{mvs}{m}{n}{<-> fmvr8x}{} \def\mvs{\usefont{OT1}{mvs}{m}{n}} \def\mvchr{\mvs\char} \def\Lightning{{\mvchr69}} \newcommand{\blitz}{\text{\Lightning}}\parindent0pt \begin{document} % ------------------Kopf- und Fußzeile-------------------------------- \lhead{SS 2000 Theoretische Informatik 2} \chead{Blatt 4} \rhead{Seite \thepage} \lfoot{} \cfoot{} \rfoot{} % ------------------Dokument------------------------------------------ \section*{Aufgabe 12} $R$ ist eine reguläre Sprache. Es soll gezeigt werden, daß $FH(R) \stackrel{\text{def}}{=} \{ x | \exists y \in \Sigma^*: (|x| = |y| \wedge xy \in R) \}$, wobei $FH$ für \emph{"`First Half"'} steht, also die erste Hälfte des Wortes. \textbf{Idee:} Sei $M$ ein DFA, der $R$ akzeptiert. Dieser DFA soll die erste Hälfte des Wortes, $x$, verarbeiten. Sobald $x$ abgearbeitet ist, befindet sich der DFA in einem Zustand $p$. Ab diesem Zustand ist der Nachfolgezustand irrelevant, der Automat muß nur nach Abarbeitung von $y$ mit $|y| = |x|$ in einem akzeptierenden Zustand $F$ sein. Man kann sich dies so vorstellen, daß man gleichzeitig in $q_0$ und in $F$ startet, wobei von $F$ aus das Reversal-Wort $y^R$ abgearbeitet wird. Wenn die beiden Teilautomaten sich in $p$ treffen, wird das Wort akzeptiert. \begin{center} \includegraphics{Blatt04-Darstellung-12.eps} \end{center} Da $R \subset \Sigma^*$ eine reguläre Sprache ist, gibt es einen DFA $M = (Q, \Sigma, \delta, q_0, F)$ mit $T(M) = R$. Man kontruiere einen NFA $M' = (Q', \Sigma, \delta', q_0', F')$ mit $Q' = \{ \underbrace{[p,q]}_{Q \times Q} |p,q \in Q \} \cup \{ q_0' \}, q_0 \notin Q \times Q$. $\delta'([p,q], \sigma) = \{ [\delta(p,\sigma),q'] | \exists \xi \in \Sigma: \delta(q,\xi) = q \}$ für alle $[p,q] \in Q', \sigma \in \Sigma$. $\delta'(q_0, \sigma) = \bigcup_{f \in F}([q_0,f], \sigma)$ für alle $\sigma \in \Sigma$. $F' = \{[q,q]|q \in Q \} \cup \{q_0'|q_0 \in F \}$. Durch Induktion nach $|w|$ zeigt man: $\forall x \in \Sigma^+$ gibt es ein $p,q \in Q$. \footnote{Das leere Wort ist nicht enthalten, da es mit $\Sigma$ in $q_0'$ liegt} $\delta'(q_0',x) = [p,q] \Leftrightarrow \delta(q_0,x) = p \wedge \exists y \in \Sigma^*, f \in F: (|x|=|y| \wedge \delta(q,y)=f$. Damit gilt für alle $x \in \Sigma^+$: \begin{eqnarray*} x \in T(M') &\Leftrightarrow& \delta'(q_0',x) \cap F' \neq \emptyset\\ &\Leftrightarrow& \exists [p,q] \in F', [p,q] \in \delta'(q_0',x)\\ &\Leftrightarrow& \exists [q,q] \in Q': [q,q] \in \delta'(q_0',x)\\ &\Leftrightarrow& \exists [q,q] \in Q': \delta(q_0,x)=q \wedge \exists y \in \Sigma^*, f \in F: |x|=|y|\wedge \delta(q,y)=f\\ &\Leftrightarrow& \exists y \in \Sigma^*, q \in Q, f \in F: \delta(q_0,x) = q \wedge \delta(q,y) = f \wedge |x| = |y|\\ &\Leftrightarrow& \exists y \in \Sigma^*: |x| = |y| \wedge xy \in T(M)\\ &\Leftrightarrow& x \in FH(T(M)) \end{eqnarray*} Wegen $\varepsilon \in T(M') \Leftrightarrow \varepsilon \in T(M)$ gilt $T(M') = FH(T(M))$. $\Box$ \section*{Aufgabe 13} Im Schaubild sieht der NFA wie folgt aus: \begin{center} \includegraphics{Blatt04-NFA-13.eps} \end{center} Daraus läßt sich mit der Potenzmengenkonstruktion der folgende DFA erstellen. Die Zustände werden der Einfachheit halber etwas "`umgetauft"': \begin{center} \includegraphics{Blatt04-DFA-13.eps} \end{center} Dieser Automat wird nach dem bekannten Verfahren minimiert. Die Klassen der Äquivalenzrelation $\stackrel{0}{\sim}$ entsprechen den Mengen der Nicht-Ziel- und der Zielzustände: $\stackrel{0}{\sim}$:\hspace{1cm}$[0,3,5]$\hspace{1cm}$[1,2,4,6,7]$ Für die weiteren Äquivalenzrelationen werden die Klassen gemäß dem Verfahren aus dem Skript ermittelt, bis sich schließlich keine neuen Klassen mehr ergeben: $\stackrel{1}{\sim}$: \begin{center} \begin{tabular}{l|l|l} & a & b \\ \hline 0 & $[1,2,4,6,7]_{\stackrel{0}{\sim}}$ & $[0,3,5]_{\stackrel{0}{\sim}}$ \\ 1 & $[0,3,5]_{\stackrel{0}{\sim}}$ & $[1,2,4,6,7]_{\stackrel{0}{\sim}}$ \\ 2 & $[0,3,5]_{\stackrel{0}{\sim}}$ & $[1,2,4,6,7]_{\stackrel{0}{\sim}}$ \\ 3 & $[0,3,5]_{\stackrel{0}{\sim}}$ & $[1,2,4,6,7]_{\stackrel{0}{\sim}}$ \\ 4 & $[1,2,4,6,7]_{\stackrel{0}{\sim}}$ & $[0,3,5]_{\stackrel{0}{\sim}}$ \\ 5 & $[1,2,4,6,7]_{\stackrel{0}{\sim}}$ & $[1,2,4,6,7]_{\stackrel{0}{\sim}}$ \\ 6 & $[0,3,5]_{\stackrel{0}{\sim}}$ & $[1,2,4,6,7]_{\stackrel{0}{\sim}}$ \\ 7 & $[1,2,4,6,7]_{\stackrel{0}{\sim}}$ & $[1,2,4,6,7]_{\stackrel{0}{\sim}}$ \\ \end{tabular} \end{center} Zu den Klassen von $\stackrel{1}{\sim}$ können nun alle Zustände zusammengefaßt werden, die gleiche Zeilen haben und bereits bei $\stackrel{0}{\sim}$ in einer Klasse waren; dies sind hier \begin{center} $[0]$\hspace{1cm}$[1,2,6]$\hspace{1cm}$[3]$\hspace{1cm}$[4]$\hspace{1cm}$[5]$ \hspace{1cm}$[6]$\hspace{1cm}$[7]$ \end{center} $\stackrel{2}{\sim}$: \begin{center} \begin{tabular}{l|l|l} & a & b \\ \hline 0 & $[1,2,6]_{\stackrel{1}{\sim}}$ & $[0]_{\stackrel{1}{\sim}}$ \\ 1 & $[3]_{\stackrel{1}{\sim}}$ & $[1,2,6]_{\stackrel{1}{\sim}}$ \\ 2 & $[3]_{\stackrel{1}{\sim}}$ & $[1,2,6]_{\stackrel{1}{\sim}}$ \\ 3 & $[3]_{\stackrel{1}{\sim}}$ & $[4]_{\stackrel{1}{\sim}}$ \\ 4 & $[1,2,6]_{\stackrel{1}{\sim}}$ & $[5]_{\stackrel{1}{\sim}}$ \\ 5 & $[1,2,6]_{\stackrel{1}{\sim}}$ & $[4]_{\stackrel{1}{\sim}}$ \\ 6 & $[3]_{\stackrel{1}{\sim}}$ & $[7]_{\stackrel{1}{\sim}}$ \\ 7 & $[1,2,6]_{\stackrel{1}{\sim}}$ & $[7]_{\stackrel{1}{\sim}}$ \\ \end{tabular} \end{center} Damit sind die Klassen von $\stackrel{2}{\sim}$: \hspace{1cm}$[0]$\hspace{1cm}$[1,2]$\hspace{1cm}$[3]$\hspace{1cm}$[4] $\hspace{1cm}$[5]$\hspace{1cm}$[6]$\hspace{1cm}$[7]$ $\stackrel{3}{\sim}$: \begin{center} \begin{tabular}{l|l|l} & a & b \\ \hline 0 & $[1,2]_{\stackrel{2}{\sim}}$ & $[0]_{\stackrel{2}{\sim}}$ \\ 1 & $[3]_{\stackrel{2}{\sim}}$ & $[1,2]_{\stackrel{2}{\sim}}$ \\ 2 & $[3]_{\stackrel{2}{\sim}}$ & $[1,2]_{\stackrel{2}{\sim}}$ \\ 3 & $[3]_{\stackrel{2}{\sim}}$ & $[4]_{\stackrel{2}{\sim}}$ \\ 4 & $[6]_{\stackrel{2}{\sim}}$ & $[5]_{\stackrel{2}{\sim}}$ \\ 5 & $[1,2]_{\stackrel{2}{\sim}}$ & $[4]_{\stackrel{2}{\sim}}$ \\ 6 & $[3]_{\stackrel{2}{\sim}}$ & $[7]_{\stackrel{2}{\sim}}$ \\ 7 & $[1,2]_{\stackrel{2}{\sim}}$ & $[7]_{\stackrel{2}{\sim}}$ \\ \end{tabular} \end{center} Damit sind die Klassen von $\stackrel{3}{\sim}$: \hspace{1cm}$[0]$\hspace{1cm}$[1,2]$\hspace{1cm}$[3]$\hspace{1cm}$[4] $\hspace{1cm}$[5]$\hspace{1cm}$[6]$\hspace{1cm}$[7]$ Die Klassen von $\stackrel{3}{\sim}$ sind jetzt identisch zu den Klassen von $\stackrel{2}{\sim}$, d.h.~$\stackrel{3}{\sim} = \stackrel{2}{\sim} = \sim$, das Verfahren endet hier. Der minimierte Automat sieht also so aus: \begin{center} \includegraphics{Blatt04-DFA-minimiert-13.eps} \end{center} \section*{Aufgabe 14} \textbf{a)} Der NFA, der $L_n$ akzeptiert, könnte wie folgt aussehen: \begin{center} \includegraphics{Blatt04-Darstellung-14.eps} \end{center} Nach dem Startzustand $q_0$ kommen zunächst maximal $n-1$ Zustände $q_i$, in denen das Teilwort $x$ verarbeitet wird. Spätestens nach $q_{n-1}$ muß dann die 1 kommen. Mit der 1 wird in Zustand $p_0$ gewechselt, ab dem die Abarbeitung von $y$ beginnt. Nach $p_0$ müssen genau $n$ Zeichen kommen, damit der Automat im akzeptierenden Zustand $p_n$ landet. Durch Induktion wird für alle $w \in \Sigma^*$ gezeigt: $q_i \in \delta(q_0,w) \Leftrightarrow |w| = i \wedge 0 \leq |w| \leq n-1$. $p_i \in \delta(q_0,w) \Leftrightarrow w = w'1w'' \wedge |w''| = i, 0 \leq |w''| \leq n, 0 \leq |w'| \leq n-1$. \begin{eqnarray*} w \in T(M) &\Leftrightarrow& \delta(q_0,w) \cap F \neq \emptyset\\ &\Leftrightarrow& p_n \in \delta(q_0,w)\\ &\Leftrightarrow& w = w'1w'', |w''| = n, 0 \leq |w'| \leq n-1\\ &\Leftrightarrow& w \in L_n~~\Box \end{eqnarray*} \textbf{b)} Sei $M = (Q, \Sigma, \delta, q_0, F)$ ein beliebiger NFA für $L_n$. Zu zeigen: $|Q| \geq 2n + 1$. \emph{Annahme:} $|Q| \leq 2n + 1$. Offensichtlich ist $L_n$ endlich und die maximale Länge eines $w \in L$ beträgt $|w| = 2n$. Man betrachte ein solches $w$ mit maximaler Länge. \emph{Behauptung:} \begin{displaymath} \forall i: 0 \leq i \leq 2n: w = w_i'w_i'', |w_i'| = i, |w_i''| = 2n - i: \exists q_i \in Q: \delta(q_0, w_i') \ni q_i \wedge \delta(q_0,w) \cap F \neq \emptyset \end{displaymath} \emph{Beweis:} Angenommen, $q_i$ existiert nicht. Dann ist $\delta(q_0,w) \cap F = \emptyset~~\blitz$. Wegen $|Q| < 2n+1$ gibt es ein $i,j,i < j$ mit $q_i = q_j = p$. Es folgt \begin{eqnarray} &&p \in \delta(q_0,w_j') \wedge |w_j'| = j \\ &&p \in \delta(q_0,w_i') \wedge |w_i'| = i \\ &&\delta(p, w_j'') \cap F \neq \emptyset \wedge |w_j''| = 2n-j\\ &&\delta(p,w_i'') \cap F \neq \emptyset \wedge |w_i''| = 2n-i\\ &\text{Aus (1) und (4) folgt} &\delta(q_0, w_j'w_i'') \supseteq \delta(p,w_i'')\\ &\Rightarrow& \delta(q_0, w_j'w_i'') \cap F \neq \emptyset \end{eqnarray} Also folgt $w_j'w_i'' \in T(M)$. Es ist aber $|w_j'w_i''| = 2n - i + j > 2n+1~~\blitz$ \textbf{c)} Jeder DFA für $L_n$ hat mehr als $2^{n+1}$ Zustände. Seien $w_1, w_2 \in L_n$ mit $w_1 \neq w_2$. Dann ist $w_1 = a_ra_{r-1}\dots a_2a_1$ und $w_2 = b_sb_{s-1}\dots b_2b_1$ mit o.B.d.A.~$1 \leq r, s \leq n, a_i, b_i \in \Sigma$. \begin{itemize} \item $r \neq s$: mit $u = 0^{n-r-1}$ gilt $w_1u \in L_n$ aber $w_2u \notin L_n$ wegen $|w_2u| > 2n \\ \Rightarrow \delta(q_0,w_1) \neq \delta(q_0, w_2)$ \item $r = s: u = 0^{n-i-1}$. $\delta(q_0,w_1u) \neq \delta(q_0,w_2u)$ \end{itemize} Also $2^{n+1}-2$ Worte plus akzeptierender Zustand plus Startzustand sind $2^{n+1}$. Rest analog zu Skript. \section*{Aufgabe 15} Die drei Aussagen entsprechen im Wesentlichen dem Satz von Myhill-Nerode, bis auf die Definition der Relation. Der Beweis kann daher in weiten Teilen analog zum Skript geführt werden. "`$1 \Rightarrow 2$"': Sei $R \subseteq \Sigma^*$ eine reguläre Sprache. Dann existiert ein DFA $M = (Q, \Sigma, \delta, q_0, F)$ mit $T(M) = R$. Für jedes $x \in \Sigma^*$ definiert man $\delta_x: Q \rightarrow Q$ vermöge $\delta_x(q) = \delta(q,x)$ für alle $q \in Q$. Man definiere die Relation $\sim: \sim \subseteq (\Sigma^* \times \Sigma^*)$ wie folgt: \begin{eqnarray*} x \sim y &\Leftrightarrow& \delta_x = \delta_y \\ &\Leftrightarrow& \forall q \in Q: \delta(q,x) = \delta(q,y) \end{eqnarray*} Reflexivität und Symmetrie: $\checkmark$ Transitivität: Sei $x \sim y$ und $y \sim z$. Dann ist $\delta_x = \delta_y$ und $\delta_y = \delta_z$, d.h.~es gilt auch $\delta_x = \delta_z$ und damit $x \sim z$. Also ist $\sim$ transitiv und eine Äquivalenzrelation. Für jedes $x,y \in \Sigma^*$ und $q \in Q$ gilt $\delta_{xy}(q) = \delta(q,xy) = \delta(\delta(q,x),y) = \delta_y(\delta_x(q)) = \delta_x \circ d_y(q)$. Also ist $\delta_{xy} = \delta_x \circ \delta_y$. Sei $x \sim y$ und $z \in \Sigma^*$ beliebig. Es gilt $\delta_{xz} = \delta_x \circ \delta_z = \delta_y \circ \delta_z = \delta_{yz}$. Damit ist $xz \sim yz$, und $\sim$ ist rechtsinvariant. Ebenso gilt $\delta_{zx} = \delta_z = \delta_x = \delta_z \circ \delta_y = \delta_{zy}$. Damit ist $\sim$ linksinvariant, also eine Kongruenzrelation. $Q \rightarrow Q$: Es gibt $|Q| \cdot |Q|$ viele verschiedene Funktionen von $Q \rightarrow Q$. Damit ist der Index von $\sim$ endlich. Es ist außerdem $T(M) = \{ \langle x \rangle_{\sim}|\delta_x(q_0) \in F \}~~\Box$ \end{document}