\documentclass[12pt,a4paper]{article} \usepackage{german} \usepackage[latin1]{inputenc} \usepackage{fancyhdr} \usepackage{amstext,amssymb} \usepackage{graphicx} \usepackage{fancybox} \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 6} \rhead{Seite \thepage} \lfoot{} \cfoot{} \rfoot{} % ------------------Dokument------------------------------------------ \section*{Aufgabe 20} \textbf{a)} \emph{Behauptung:} $L_1 \stackrel{\text{Def}}{=} \{ wcw | w \in \{ 0, 1 \}^n \}$ für ein festes $n \in \mathbb{N}$ ist eine reguläre Sprache. \emph{Beweis:} Man betrachte DFAs $M_i$, die genau 1 Wort aus $L_1$ erkennen. Z.B.~$n=2$: $M_1$ akzeptiert $\{ 00c00 \},~M_2~\{ 01c01 \},~ M_3~\{ 10c10 \},~M_4~\{ 11c11 \}$. Zu einem gegebenen $n \in \mathbb{N}$ gibt es also genau $2^n$ solcher $M_i$'s, also endlich viele. $L_1$ ist dann die endliche Vereinigung regulärer Mengen und damit ebenfalls regulär. \textbf{b)} \emph{Behauptung:} $L_2 \stackrel{\text{Def}}{=} \{ wcw | w \in \{ 0, 1 \}^* \}$ ist \emph{nicht} regulär. \emph{Beweis:} Angenommen, $L_2$ sei regulär. Dann gibt es nach dem Pumping-Lemma eine Konstante $n \in \mathbb{N}$ und für das Wort $\{ 0^nc0^n \} \in L_2$ gibt es eine Zerlegung $0^nc0^n = xyz$ mit $0 \leq |y| \leq n$ und $xy^iz \in L_2$ für alle $i \geq 0$. Drei mögliche Fälle können eintreten: \begin{enumerate} \item $y$ enthält ein $c$, dann enthält $xy^2z \in L_2~2c~~\blitz$ \item $y$ enthält kein $c$, $z$ enthält ein $c$. Dann befinden sich durch Pumpen links vom $c$ mehr Nullen als rechts $\Rightarrow$ Wort nicht in $L_2~~\blitz$ \item Analog zu 2: $y$ enthält kein $c$, $x$ enthält ein $c$. Durch Pumpen befinden sich rechts vom $c$ mehr Nullen als links $\Rightarrow$ Wort nicht in $L_2~~\blitz$ \end{enumerate} Damit ist $L_2$ keine reguläre Sprache. \textbf{c)} \emph{Behauptung:} $L_3 \stackrel{\text{Def}}{=} \{ w \in \{0\}^*|~|w| \neq 2^n~\forall~n \in \mathbb{N}\}$ ist keine reguläre Sprache. \emph{Beweis:} Angenommen, $L_3$ sei regulär. Dann ist auch das Komplement $\overline{L_3} = \{ w \in \{0\}^* |~|w| = 2^n~\forall~n \in \mathbb{N}\}$ eine reguläre Sprache. Sei $n$ die Konstante des Pumping-Lemmas und $2^m > n$. Dann besitzt $w = 0^{2^m}$ eine Zerlegung $w = xyz$ mit $0 \leq |y| \leq n$ und $xy^2z \in \overline{L_3}$, d.h.~$|xy^2z|$ ist die Zerlegung. Es gilt: $2^m < 2^m+1 \leq |xy^2z| < 2^m+n < 2^m + 2^m = 2^m \cdot 2 = 2^{m+1} \Rightarrow |xy^2z|$ ist keine Zweier-Potenz$~~\blitz$ \textbf{d)} \emph{Behauptung}: $L_4 \stackrel{\text{Def}}{=} \{ ww^R | w \in \{0,1\}^* \}$ ist keine reguläre Sprache. \emph{Beweis:} Über Abschlußeigenschaften. Angenommen, $L_4$ ist regulär. Dann ist auch $L_4' = L_4 \cap \{ 0^r1^s0^n | r,s,n \geq 0 \} = \{ 0^n1^{2r}0^n | n,r \geq 0 \}$ regulär. Man betrachte einen Homomorphismus $h_1$ mit $h_1(a)=0, h_1(b)=0,h_1(1)=1$. Dann ist $L_4'' = h^{-1}_1(L_4') \cap \{ a^r1^sb^n | r,s,n \geq 0 \} = \{ a^n1^{2r}b^n \}$ ebenfalls regulär. Man betrachte einen weiteren Homomorphismus $h_2$ mit $h_2(a)=a, h_2(1)=\varepsilon, h_2(b) = b$. Dann ist $h_2(L_4'') = \{ a^nb^n | n \geq 0 \}$ ebenfalls regulär$~~\blitz$ \section*{Aufgabe 21} \emph{Behauptung:} $L \stackrel{\text{Def}}{=} \{ 0^i1^j | i,j \geq 1 \wedge \text{ggT} (i,j)=1 \}$ ist nicht regulär. \emph{Beweis:} Angenommen, $L$ sei regulär. Dann gibt es nach dem Pumping-Lemma ein $n \in \mathbb{N}$, so daß für $w \in L$ mit $|w| \geq n$ gilt: $w=xyz, 0 < |y| < n, xy^iz \in L~\forall~i \geq 0$. Sei $w = 0^n1^{n'}$ mit $n'$ ist die kleinste Primzahl größer als $n$. Dann ist ggT$(n,n') = 1 \Rightarrow w \in L$. Es ist $|w| \geq n$, also gibt es die Zerlegung $w = xyz$. Angenommen, $y$ enthalte Nullen und Einsen. Dies würde einen Widerspruch beim Pumpen ergeben, da das resultierende Wort nicht mehr in $L$ wäre. $y$ enthält also entweder nur Nullen oder nur Einsen. o.B.d.A. enthalte $y$ nur Nullen. Dann ist $w=xyz_1z_2$ mit $z_1 \in \{0\}^*, z_2 \in \{1\}^*$. $|xyz_1| = n$ und $z_2 = n' \Rightarrow n = |y|+|xz_1| = s+r$ mit $00$. $n'$ ist eine Primzahl $\Rightarrow \text{ggT}(s,n')=1$. Nach Folgerung aus dem gegebenen Satz gibt es $u,v \in \mathbb{Z}$ mit $n < 0, r > 0$ und $us + vn' = 1$. $u < 0 \Rightarrow u = -|n|$. \begin{eqnarray*} us + rn' = 1 &\Leftrightarrow& urs + vrn' = r \\ &\Leftrightarrow& -|n|rs + vrn' = r \\ &\Leftrightarrow& r|n|s + r = vrn' \end{eqnarray*} mit $r,|n|, s, v > 0$. Nach dem Pumping-Lemma gilt $xy^{r|u|}z \in L$, d.h.~ggT$(|xy^{r|u|}z_1|, |z_1|) = 1$. Aber: $|xy^{r|u|}z_1| = |y|r|u|+|xz_1| = sr|u|+r$ und ggT$(|xy^{r|u|}z_1|,|z_2|) = \text{ggT}(sr|u|+r, n') = \text{ggT}(vrn', n') = n' > 1~~\blitz$ \section*{Aufgabe 22} \textbf{a)} $G = (V,\Sigma, P, S)$ mit $V = \{S\}$, $\Sigma=\{ \text{op}, (, ), \cdot, + \}$,\\ $P = \{ S \rightarrow \text{op}, S \rightarrow S+S, S \rightarrow S \cdot S, S \rightarrow (S) \}$ \textbf{b)} \emph{Behauptung:} $L(G) = L$. \emph{Beweis:} Sei $w \in \Sigma^*$. Zu zeigen: $S \stackrel{*}{\Rightarrow} w \Leftrightarrow w$ ist ein korrekt geformter arithmetischer Ausdruck~$(*)$ Beweis durch Induktion nach $|w|$: Verankerung: $|w| = 1$. "`$\Rightarrow$"': $S \stackrel{*}{\Rightarrow} w$ mit $|w|=1 \Rightarrow w= \text{op} \Rightarrow w$ ist ein korrekt geformter Ausdruck.$~~\checkmark$ "`$\Leftarrow$"': $w = op$ ist der einzige korrekt geformte Ausdruck mit der Länge 1.$~~\checkmark$ $|w| = n+1$: $(*)$ gilt für $|w'| \leq n$. "`$\Rightarrow$"': $S \stackrel{*}{\Rightarrow}w, |w| > 1 \Rightarrow w \neq \text{op}$, also gibt es 3 Fälle: \begin{enumerate} \item $S \rightarrow S+S \stackrel{*}{\Rightarrow} w_1 + w_2 = w$ mit $S \stackrel{*}{\Rightarrow} w_1, S \stackrel{*}{\Rightarrow} w_2$ \item $S \rightarrow S\cdot S \stackrel{*}{\Rightarrow} w_1 \cdot w_1 = w$ \item $S \rightarrow (S) \stackrel{*}{\Rightarrow} (w_1) = w$ \end{enumerate} In jedem Fall ist $|w_1| \leq n, |w_2| \leq n$, damit sind $w_1$ und $w_2$ nach Induktionsvorraussetzung korrekt geformt und damit auch $w_1 + w_2, w_1 \cdot w_2, (w_1)~~\checkmark$ "`$\Leftarrow$"': $w$ ist ein korrekt geformter Ausdruck der Länge $n+1$. Damit enthält $w$ nicht nur op, sondern mindestens ein $+,\cdot$ oder Klammern. \vspace{1ex}\hspace*{0.4em} \begin{math} \left. \begin{array}{ll} 1. & w = w_1 + w_2\\[1ex] 2. & w = w_1 \cdot w_2\\[1ex] 3. & w = (w_1)\\[1ex] \end{array} \right\} w_1 \text{ und } w_2 \text{ sind korrekt geformte Ausdrücke } \leq n \end{math} Nach Induktionsvorraussetzung gilt: $S \stackrel{*}{\Rightarrow} w_1, S \stackrel{*}{\Rightarrow} w_2$. Damit gilt \begin{enumerate} \item $S \rightarrow S + S \stackrel{*}{\Rightarrow} w_1 + S \stackrel{*}{\Rightarrow} w_1 + w_2 = w$ \item $S \rightarrow S \cdot S \stackrel{*}{\Rightarrow} w_1 \cdot S \stackrel{*}{\Rightarrow} w_1 \cdot w_2 = w$ \item $S \rightarrow (S) \stackrel{*}{\Rightarrow} (w_1) = w$ \end{enumerate} Es gilt also immer: $S \stackrel{*}{\Rightarrow} w$ mit $|w| = n+1~~\Box$ \section*{Aufgabe 23} Die Grammatik $G = ( \{ S,A,B,C,D,E \}, \{a,b\}, P,S )$ mit \[ P \stackrel{\text{Def}}{=} \left\{ \begin{array}{ll} S \rightarrow AE | BE | C & A \rightarrow aAa|B \\ B \rightarrow bB | bb & C \rightarrow aCaa|D\\ D \rightarrow baD|abD|aa & E \rightarrow EE|\varepsilon \end{array} \right\}\] ist in eine reduzierte kontextfreie Grammatik zu überführen. Nach Satz S.~53 im Skript ist eine kontextfreie Grammatik reduziert, wenn \begin{enumerate} \item $\forall~ A \in \{ V-\Sigma \}: (A \rightarrow \varepsilon) \notin P$ \item $S \rightarrow \varepsilon \Leftrightarrow \varepsilon \in L$ \item $S$ erscheint auf \emph{keiner} rechten Seite. \end{enumerate} \textbf{1. Schritt:} Anwendung Algorithmus S.~53 $V_1 =\{ E \}\hspace{1cm}V_2 = \{ E \} \cup \{ E \} \Rightarrow V_n = \{ E \}$ $P_1 = P \cup \{ S \rightarrow A, S \rightarrow B, E \rightarrow E\\ P_2 = P_1 \setminus \{ E \rightarrow E \}\\ P' = P_2 \cup \{ S' \rightarrow S \}$ Man erhält $G' = ( \{ S, S', A, B, C, D, E \}, \{a, b\}, P', S')$ \[ P' = \left\{ \begin{array}{ll} S \rightarrow AE | BE | C | A | B & A \rightarrow aAa|B \\ B \rightarrow bB | bb & C \rightarrow aaCaa|D \\ D \rightarrow baD|abD|aa & E \rightarrow EE|E\\ S' \rightarrow S \end{array} \right\} \] $G'$ erfüllt die gewünschten Eigenschaften. \textbf{2. Schritt:} Anwendung Algorithmus S.~59; Beseitigung zyklischer Produktionen $V_{S'}^{(1)} = \{ S \} \\ V_{S'}^{(2)} = \{ S \} \cup \{ A,B,C \} = \{ S,A,B,C \} \\ V_{S'}^{(3)} = \{ S,A,B,C \} \cup \{ A,B,C,D \} = \{S,A,B,C,D\}\\ V_{S'}^{(4)} = \{ S,A,B,C,D \} \cup \{ A,B,C,D \} = \{S,A,B,C,D \} = V_{S'}^{(N)}\\[3ex] V_S^{(1)} = \{ A,B,C \}\\ V_S^{(2)} = \{ A,B,C,D \}\\ V_S^{(3)} = \{ A,B,C,D \} = V_S^{(N)}\\[3ex] V_A^{(1)} = \{ B \}\\ V_A^{(2)} = \{ B \} = V_A^{(N)}\\[3ex] V_B^{(1)} = \emptyset = V_B^{(N)}\\[3ex] V_C^{(1)} = \{ D \}\\ V_C^{(2)} = \{ D \} = V_C^{(N)}\\[3ex] V_D^{(1)} = \emptyset = V_D{(N)}\\[3ex] V_E^{(1)} = \{ E \}\\ V_E^{(2)} = \{ E \} = V_E^{(N)} $ $G'' = ( \{S', S, A, B, C, D, E \}, \{ a,b \}, P'', S' )$ $P'' = ( P' \setminus \{ S \rightarrow A|B|C, A \rightarrow B, C \rightarrow D, E \rightarrow E, S' \rightarrow S \})\\ \cup \{ S' \rightarrow AE|BE|aAa|bB|bb|aCaa|baD|abD|aa,\\ \hspace*{7mm}S \rightarrow aAa|bB|bb|aCaa|baD|abD|aa,\\ \hspace*{6.5mm}A \rightarrow bB, C \rightarrow baD|abD|aa, E \rightarrow EE \}$ Nach Skript S.~56 erhalten wir: \[ P'' = \left\{ \begin{array}{l} S' \rightarrow AE|BE|aAa|bB|bb|aCaa|baD|abD|aa \\ S \rightarrow AE|BE|aAa|bB|bb|aCaa|baD|abD|aa \\ A \rightarrow aAa|bB|bb\\ B \rightarrow bB|bb\\ C \rightarrow baD|abD|aCaa|aa\\ D \rightarrow baD|abD|aa\\ E \rightarrow EE \end{array} \right\} \] \textbf{Schritt 3:} Skript S.~55; Beseitigen überflüssiger Symbole \Ovalbox{1} $V_1 = \{ S',S,A,B,C,D \}\\ V_2 = \{ S', S,A,B,C,D \} = V_N\\ \overline{G} = ( \overline{V}, \{a,b\}, \overline{P}, S')\\ \overline{V} = \{ S',S,A,B,C,D \} \cup \{a,b\}\\ \overline{P} = P'' \cap (\overline{V} \times \overline{V}^*)\\[3ex] \leadsto \overline{P} = P'' \setminus \{ S' \rightarrow AE|BE, S \rightarrow AE|BE, E \rightarrow EE\}$ \Ovalbox{2} $H_0 = \{ S' \}\\ H_1 = \{ S' \} \cup \{ A,B,C,D \} = \{ S',A,B,C,D \}\\ H_2 = \{ S',A,B,C,D \} = H_N\\ G''' = (V''',\{a,b\}, P''', S') \text{ mit}\\ V''' = \{S',A,B,C,D\} \cup \{a,b'\}, P''' = \overline{P} \cap (V''' \times (V''')^*)\\[3ex] \leadsto P''' = \left\{ \begin{array}{l} S' \rightarrow aAa|bB|bb|aCaa|baD|abD|aa\\ A \rightarrow aAa|bB|bb\\ B \rightarrow bB|bb\\ C \rightarrow aCaa|baD|abD|aa\\ D \rightarrow baD|abD|aa \end{array} \right\}$ \section*{zu Aufgabe 21} In der Aufgabenstellung war folgender Satz gegeben: \[ \text{Zu } i,j \in \mathbb{Z} \text{ existieren } u,v \in \mathbb{Z} \text{ mit } ui+vj = 1\] Daraus läßt sich folgende Folgerung ableiten: \[ \text{Zu } i,j \in \mathbb{N}~(i,j \geq 1) \text{ mit ggT}(i,j)=1 \text{ gibt es }u,v \in \mathbb{Z} \text{ mit } uv+vj=1 \text{ und } u<0, v>0 \] \textbf{Beweis:} Nach dem Satz existieren $u,v \in \mathbb{Z}$ mit $ui+vj = 1$. Da $i > 0, j > 0$ ist $u \leq 0$ und $v \geq 0$ oder $u \geq 0$ und $v \leq 0$. Für den ersten Fall ist die Folgerung bereits bewiesen. Sei also $u \geq v$ und $r \leq 0$, dann gilt \begin{eqnarray*} ui+vj = 1 &\Leftrightarrow& ui-uij+uij+vj = 1\\ &\Leftrightarrow& i(u-uj)+j(v+ui) = 1 \text{ mit } (u-uj) =: u' \leq 0 \text{ und }(v+ui) =: v' \geq 0 \end{eqnarray*} Also ist $u'i+v'j = 1~~\Box$ Es soll gelten $u < 0, v > 0$ bzw.~$u' < 0, v' > 0$. \begin{eqnarray*} &&u = 0 \Rightarrow vj=1 \Rightarrow j=1~~\blitz\\ &&v = 0 \Rightarrow ui=1 \Rightarrow i=1~~\blitz\\ &&u' = 0 \Rightarrow n-nj = 0 \Rightarrow j=1~~\blitz\\ &&v' = 0 \Rightarrow v' = -ui \Rightarrow -v+vj=1 \Rightarrow v(j-1)=1 \Rightarrow j = \frac{1}{r}+1 \Rightarrow i=0, \text{ da } r < 0~~\blitz \end{eqnarray*} \end{document}