\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 5} \rhead{Seite \thepage} \lfoot{} \cfoot{} \rfoot{} % ------------------Dokument------------------------------------------ \section*{Aufgabe 16} Der Automat $M$ sieht im Schaubild wie folgt aus: \begin{center} \includegraphics{Blatt05-DFA-Aufg16.eps} \end{center} Damit der Algorithmus aus Hopcroft/Ullman allerdings funktioniert, \textbf{muß} der Startzustand mit dem Index \textbf{1} beginnen, da es wegen der Rekursionsbedingung sonst zu Fehlern kommen kann, weil $R^0_{ij}$ den Zustandsübergang unter Verwendung von \textbf{keinen} Zwischenzuständen (auch nicht Zustand 0) darstellt. Nach Hopcroft/Ullman lassen sich bestimmte Abschnitte des Automaten durch den regulären Ausdruck $R^k_{ij}$ beschreiben. Dieser Ausdruck beschreibt die Wörter, mit denen man vom Zustand $i$ nach Zustand $j$ gelangen kann, wobei aber keine Zustände als Zwischenschritte benutzt werden dürfen, die einen höheren Index als $k$ haben. Der gesuchte reguläre Ausdruck lautet demnach $R^4_{14}$. Dieser Ausdruck läßt sich rekursiv berechnen. Für $R^0_{ij}$ wird der Ausdruck wie folgt definiert: \begin{displaymath} R^0_{ij} = \left\{ \begin{array}{ll} \{ a | \delta(q_i,a) = q_j \} & \text{falls } i \neq j \\ \{ a | \delta(q_i,a) = q_j \} \cup \{ \varepsilon \} & \text{falls } i = j \end{array} \right. \end{displaymath} Wenn $i=j$ besteht der reguläre Ausdruck für diesen Zustand (der Übergang vom Zustand in sich selbst) also immer mindestens aus $\varepsilon$. $R^k_{ij}$ wird rekursiv wie folgt definiert: \[ R^k_{ij} = R^{k-1}_{ik}(R^{k-1}_{kk})^*R^{k-1}_{kj} \cup R^{k-1}_{ij} \] Dies bedeutet: $R^k_{ij}$ besteht aus einer Zeichenkette, die von Zustand $i$ in Zustand $j$ führt, wobei aber nur Zustände kleiner als $k$ als Zwischenstationen benutzt werden $(= R^{k-1}_{ij})$, oder aus einer Zeichenkette, die unter Verwendung von Zwischenzuständen \textbf{kleiner} als $k$ zunächst von $i$ nach $k$ läuft $(= R^{k-1}_{ik})$, dann beliebig lange (möglicherweise auch gar nicht) in diesem Zustand bleibt $(= (R^{k-1}_{kk})^*)$, um dann von dort nach $j$ weiter zu laufen $(= R^{k-1}_{kj})$. Die 16 Ausdrücke für $R^0_{ij}$ lauten: \begin{displaymath} \begin{array}{llll} R^0_{11} = b + \varepsilon & R^0_{21} = \emptyset & R^0_{31} = a & R^0_{41} = a \\ R^0_{12} = a & R^0_{22} = a + \varepsilon & R^0_{32} = \emptyset & R^0_{42} = b \\ R^0_{13} = \emptyset & R^0_{23} = b & R^0_{33} = \varepsilon & R^0_{43} = \emptyset \\ R^0_{14} = \emptyset & R^0_{24} = \emptyset & R^0_{34} = b & R^0_{44} = \varepsilon \\ \end{array} \end{displaymath} Da man nicht unbedingt noch $3 \cdot 16$ Ausdrücke berechnen möchte, kann man sich ja mal anschauen, was man nun eigentlich effektiv braucht. Gesucht ist der Ausdruck $R^4_{14}$. \begin{displaymath} \begin{array}{l} R^4_{14} = R^3_{14}(R^3_{44})^* R^3_{44} \cup R^3_{14} \\ \hline R^3_{14} = R^2_{13}(R^2_{33})^* R^2_{34} \cup R^2_{14} \\ R^3_{44} = R^2_{43}(R^2_{33})^* R^2_{34} \cup R^2_{44} \\ \hline R^2_{13} = R^1_{12}(R^1_{22})^* R^1_{23} \cup R^1_{13} \\ R^2_{14} = R^1_{12}(R^1_{22})^* R^1_{24} \cup R^1_{14} \\ R^2_{33} = R^1_{32}(R^1_{22})^* R^1_{23} \cup R^1_{33} \\ R^2_{34} = R^1_{32}(R^1_{22})^* R^1_{24} \cup R^1_{34} \\ R^2_{43} = R^1_{42}(R^1_{22})^* R^1_{23} \cup R^1_{43} \\ R^2_{44} = R^1_{42}(R^1_{22})^* R^1_{24} \cup R^1_{44} \\ \hline R^1_{12} = R^0_{11}(R^0_{11})^* R^0_{12} \cup R^0_{12} \\ R^1_{13} = R^0_{11}(R^0_{11})^* R^0_{13} \cup R^0_{13} \\ R^1_{14} = R^0_{11}(R^0_{11})^* R^0_{14} \cup R^0_{14} \\ R^1_{22} = R^0_{21}(R^0_{11})^* R^0_{12} \cup R^0_{22} \\ R^1_{23} = R^0_{21}(R^0_{11})^* R^0_{13} \cup R^0_{23} \\ R^1_{24} = R^0_{21}(R^0_{11})^* R^0_{14} \cup R^0_{24} \\ R^1_{32} = R^0_{31}(R^0_{11})^* R^0_{12} \cup R^0_{32} \\ R^1_{33} = R^0_{31}(R^0_{11})^* R^0_{13} \cup R^0_{33} \\ R^1_{34} = R^0_{31}(R^0_{11})^* R^0_{14} \cup R^0_{34} \\ R^1_{42} = R^0_{41}(R^0_{11})^* R^0_{12} \cup R^0_{42} \\ R^1_{43} = R^0_{41}(R^0_{11})^* R^0_{13} \cup R^0_{43} \\ R^1_{44} = R^0_{41}(R^0_{11})^* R^0_{14} \cup R^0_{44} \\ \end{array} \end{displaymath} Die Ergebnisse lauten damit: \begin{displaymath} \begin{array}{ll} R^1_{12} = (b + \varepsilon) b^* a + a = b^* a + a = b^* a & R^1_{13} = b^* \emptyset + \emptyset = \emptyset \\ R^1_{14} = b^* \emptyset + \emptyset = \emptyset & R^1_{22} = \emptyset b^* a + (a + \varepsilon) = a + \varepsilon \\ R^1_{23} = \emptyset b^* \emptyset + b = b & R^1_{24} = \emptyset b^* \emptyset + \emptyset = \emptyset \\ R^1_{32} = (a b^* a) + \emptyset = ab^*a & R^1_{33} = ab^*\emptyset + \varepsilon = \varepsilon \\ R^1_{34} = ab^* \emptyset + b = b & R^1_{42} = (ab^*a) + b \\ R^1_{43} = ab^* \emptyset + \emptyset = \emptyset & R^1_{44} = a b^* \emptyset + \varepsilon = \varepsilon \\ \hline R^2_{13} = (b^*a+a)a^*b + \emptyset = b^* a^+ b & R^2_{14} = b^*a a^* \emptyset + \emptyset = \emptyset \\ R^2_{33} = ab^*a a^*b + \varepsilon = ab^*a^+b + \varepsilon & R^2_{34} = ab^*a a^* \emptyset + b = b \\ R^2_{43} = ((ab^*a)+b) a^* b + \emptyset = (ab^*a + b) a^*b & R^2_{44} = ((ab^*a) + b) a^* \emptyset + \varepsilon = \varepsilon \\ \hline R^3_{14} = b^*a^+b (ab^*a^+b)^* b & R^3_{44} = (ab^*a+b)a^*b (ab^*a^+b)^* b + \varepsilon \\ \hline \multicolumn{2}{l} {R^4_{14} = b^*a^+b(ab^*a^+b)^*b ((ab^*a+b)a^*b (ab^*a^+b)^* b)^* + b^*a^+b (ab^*a^+b)^* b} \\ \multicolumn{2}{l} {\mathbf {R^4_{14} = b^*a^+b(ab^*a^+b)^*b ((ab^*a+b)a^*b (ab^*a^+b)^* b)^*}} \end{array} \end{displaymath} Anmerkung: $(a + \varepsilon)^*$ läßt sich auskürzen zu $a^*$. Eine Konkatenation mit der leeren Menge führt dazu, daß der gesamte Teilausdruck leer ist. \section*{Aufgabe 17} $R \subseteq \Sigma^*$ ist eine reguläre Sprache. Es ist zu zeigen: $MT(R) = \{ y | \exists x,z \in \Sigma^*: |x| = |y| = |z| \wedge xyz \in R \}$ ist regulär, wobei $MT$ für \emph{Mittelteil} steht. \textbf{Beweis:} $R$ ist regulär, d.h.~es gibt einen DFA $M = (Q, \Sigma, \delta, q_0, F)$ mit $T(M) = R$. Definiert wird ein MNFA $M' = (Q', \Sigma, \delta', Q_0, F')$ mit folgenden Eigenschaften: \begin{eqnarray*} Q' &=& Q \times Q \times Q \times Q \times Q \\ Q_0 &=& \{ [q_0, p, p, q, q]| p, q \in Q \} \\ F' &=& \{ [p, p, q, q, f]| p, q \in Q, f \in F \} \\ \delta'([ q_1, q_2, q_3, q_4, q_5 ], a) &=& \{ [ \delta(q_1,\sigma), q_2, \delta(q_3,\sigma), q_4, \delta(q_5, \tau) ] , \sigma, \tau, a \in \Sigma \} \end{eqnarray*} $\delta'$ wird wie üblich auf Wörter aus $\Sigma^*$ erweitert. \textit{Behauptung:} \begin{eqnarray*} [ p_1, p_2, p_3, p_4, p_5 ] \in \delta'([q_1, q_2, q_3, q_4, q_5],w) &\Leftrightarrow& \exists~x \in \Sigma^*: |x| = |w|\\ && \wedge~ \delta(q_1,x)=p_1\\ && \wedge~ q_2 = p_2\\ && \wedge~ \delta(q_3, w) = p_3\\ && \wedge~ q_4 = p_4 \\ && \wedge~ \exists~ z \in \Sigma^*: |z| = |w|\\ && \wedge~ \delta(q_5,z) = p_5 \end{eqnarray*} \emph{Beweis} durch Induktion nach $|w|$: \begin{eqnarray*} y \in T(M') &\Leftrightarrow& \delta'(Q_0, y) \cap F' \neq \emptyset \\ &\Leftrightarrow& \exists~ p,q ,p',q' \in Q, f \in F \text{ mit } [p,p,q,q,f] \in \delta'([q_0,p',p',q'q'],y)\\ &\Leftrightarrow& \exists~ x \in \Sigma^*: (|x| = |y|)\\ && \wedge~ \delta(q_0,x) = p\\ && \wedge~ (p'=p)\\ && \wedge~ \delta(p',y)=q\\ && \wedge~ (q'=q)\\ && \wedge~ (\exists~ z \in \Sigma^*: |z| = |y|\\ && \wedge~ \delta(q',z) = f)\\ &\Leftrightarrow& \exists~ x,z \in \Sigma^*: p,q \in Q, f \in F: (\delta(q_0,xyz)\\ && =\delta(\delta(q_0, x), yz)\\ && = \delta(p, yz)\\ && =\delta(\delta( p, y), z)\\ && = \delta(q,z) = f)\\ && \wedge~ (|x| = |y| = |z|) \\ &\Leftrightarrow& \exists~ x,z \in \Sigma^*: (|x| = |y| = |z|) \wedge (xyz \in R)\\ &\Leftrightarrow& y \in MT(R) \end{eqnarray*} \emph{Induktionsverankerung:} $|w| = 0 \Rightarrow w = \varepsilon~~\checkmark$\hspace{1cm}$|w| = 1 \Rightarrow w = a \in \Sigma~~\checkmark$ \emph{Induktionsannahme:} Behauptung gilt für $|w| = n$. \emph{Induktionsschluß:} $|w| = n+1 \Rightarrow w = w_1w_2 \dots w_nw_{n+1}$, das heißt \begin{eqnarray*} [p_1, p_2, p_3, p_4, p_5] \in \delta'([q_1, q_2, q_3, q_4, q_5, ], w_1 \dots w_n) &\Leftrightarrow& \exists~ x \in \Sigma^*: |x|=n \\ && \wedge~ \delta(q_1, x) = p_1 \\ && \wedge~ (q_2 = p_2) \\ && \wedge~ \delta(q_3, w_1 \dots w_n)=p_3 \\ && \wedge~ q_n = p_n \\ && \wedge~ \exists~ z \in \Sigma^*: |z| = n \\ && \wedge~ \delta(q_5,z) = p_5 \end{eqnarray*} \begin{eqnarray*} &&\delta'([q_1, q_2, q_3, q_4, q_5], w_1 \dots w_nw_{n+1}) \\ &&= \bigcup_{[s_1, s_2, s_3, s_4, s_5]} \delta'([s_1, s_2, s_3, s_4, s_5],w_{n+1}) \in \delta'([q_1, q_2, q_3, q_4, q_5], w_1 \dots w_n)\\ && \stackrel{\text{IV}}{=} \bigcup_{[s_1, s_2, s_3, s_4, s_5] \text{ mit }(*)} \{ [\delta(s_1,\sigma), s_2, \delta(s_3, w_{n+1}), s_4, \delta(s_5, \tau)]|\sigma, \tau \in \Sigma \} \end{eqnarray*} \begin{eqnarray*} (*)\hspace{1cm} \exists~ x \in \Sigma^*: && \delta(q_1, x) = s_1\\ && \wedge~ s_2 = s_2\\ && \wedge~ \delta(q_3, w_1 \dots w_n) = s_3\\ && \wedge~ q_4 = s_4\\ && \wedge~ \exists~ z \in \Sigma^*: \delta(q_5, z)=s_5\\ && \wedge~ |x|=|z|=n \end{eqnarray*} Einsetzen: \begin{eqnarray*} &=& \{ [ \delta(\delta(q_1, x), \sigma), q_2,\\ && ~\delta(\delta(q_3, w_1 \dots w_n),w_{n+1}), q_4,\\ && ~\delta(\delta(q_5, z),\tau) ] | \sigma, \tau \in \Sigma \text{ und } \exists~ x, z \in \Sigma: |x| = |z| = n \}\\ &=& \{ [ \delta(q_1, x'), q_2, \delta(q_3, w), q_4, \delta(q_5,z') ]| \exists~ x', z' \in \Sigma^*: |x'| = |z'| = n+1 \}\\ &\Rightarrow& [p_1, p_2, p_3, p_4, p_5 ] \in \delta'([ q_1, q_2, q_3, q_4, q_5], w_1 \dots w_{n+1}) \\ &\Leftrightarrow& \exists~ x \in \Sigma^*: |x| = n+1\\ && \wedge~ \delta(q_1, x) = p_1 \\ && \wedge~ q_2 = p_2 \\ && \wedge~ \delta(q_3, w_1 \dots w_{n+1}) = p_3 \\ && \wedge~ (q_4 = p_4) \\ && \wedge~ (\exists~ z \in \Sigma^*: |z| = n+1 \wedge \delta(q_5, z) = p_5) \end{eqnarray*} Der Induktionsschritt war richtig, die Behauptung ist also wahr. \section*{Aufgabe 18} Es läßt sich intuitiv feststellen, daß die Aussagen b) und c) falsch sind, weil bei b) der Ausdruck auf der linken Seite mit einem $s$ beginnt und auf der rechten Seite mit einem $r$. Bei c) kann man mit dem Ausdruck auf der linken Seite Zeichenketten $rsrsrs\dots$ bilden, während rechts nur $rrrrr\dots$ oder $sssss\dots$ möglich sind. Beweise durch Gegenbeispiele: Seien die regulären Ausdrücke $r,s$ wie folgt belegt: $r = a, s = b$. \textbf{b)} $ba \in s(rs+s)^*r = ab \in rr^*s(rr^*s)^*~~\blitz$ \textbf{c)} $abab \in (r + s)^* = aaaa \in r^* + s^*~~\blitz$ Die Beweise für die wahren Aussagen kann ich leider nur auf Verständnisebene führen, aber nicht formal, und da das dann sowieso nix wert ist, lasse ich es einfach. Wird schon nicht in der Klausur kommen \texttt{:-/} \section*{Aufgabe 19} \textbf{a)} $L_1 \subseteq \Sigma^*$ ist regulär und $L_2 \subseteq \Sigma^*$ beliebig. \emph{Behauptung:} $L_1 / L_2 = \{ x | \exists~ y \in L_2: xy \in L_1$ ist regulär. \emph{Beweis:} Da $L_1$ regulär ist, gibt es einen DFA $M' = (Q, \Sigma, \delta, q_0, F)$ mit $T(M) = L_1$. Man definiere einen DFA $M' = (Q, \Sigma, \delta, q_0, F')$ mit $F' := \{ q \in Q | \exists~ y \in L_2: \delta(q,y) \in F \}$. Es gilt: \begin{eqnarray*} x \in T(M') &\Leftrightarrow& \delta(q_0,x) \in F' \\ &\Leftrightarrow& \delta(q_0,x)=q \wedge q \in F'\\ &\Leftrightarrow& \delta(q_0,x) = q \wedge (\exists~ y \in L_2: \delta(q,y) \in F)\\ &\Leftrightarrow& \exists~ y \in L_2: xy \in L_1\\ &\Leftrightarrow& x \in L_1 / L_2 \end{eqnarray*} Also ist $T(M') = L_1 / L_2$ und $L_1 / L_2$ somit regulär.\hspace{1cm}$\Box$ \textbf{b)} \emph{Behauptung:} Die regulären Sprachen sind nicht \textbf{nicht} abgeschlossen unter abzählbar unendlicher Vereinigung. \emph{Beweis} [durch Gegenbeispiel]: Man definiere für jedes $n \in \mathbb{N}$ die Sprache $L_n := \{ a^nb^n \}$. Jede einzelne $L_n$ ist endlich und somit eine reguläre Sprache. Allerdings ist \[ L = \bigcup_{n=0}^{\infty} \{ a^nb^n \} = \{ a^nb^n | n \geq 0 \}, \] was ja bekanntlich keine reguläre Sprache ist.\hspace{1cm}\blitz \end{document}