Mercurial > 14ss.theoinf
annotate notes/tex/grammars.tex @ 24:322b0166cc24
fix errors in GNF and pda
| author | Markus Kaiser <markus.kaiser@in.tum.de> |
|---|---|
| date | Thu, 22 May 2014 12:41:35 +0200 |
| parents | 7afd6762980f |
| children | 44fd483bde00 |
| rev | line source |
|---|---|
| 1 | 1 \defineUnit{grammatik}{% |
| 2 \begin{frame} | |
| 3 \frametitle{Grammatiken} | |
| 4 \setbeamercovered{dynamic} | |
| 5 | |
| 3 | 6 \begin{definition}[Grammatik] |
| 7 Eine \structure{(Phrasenstruktur-)Grammatik} $G = (V, \Sigma, P, S)$ ist ein 4-Tupel: | |
| 1 | 8 \begin{description} |
| 9 \item[V] endlich viele \alert{Nichtterminale} (Variablen) | |
| 10 \item[$\Sigma$] ein Alphabet von \alert{Terminalen} | |
| 3 | 11 \item[P] endlich viele \alert{Produktionen} $\subseteq \left( V \cup \Sigma \right)^* \times \left( V \cup \Sigma \right)^*$ |
| 12 \item[S] ein \alert{Startsymbol} (Axiom) | |
| 1 | 13 \end{description} |
| 3 | 14 Ist $(l, r) \in P$, so schreibt man \structure{$l \rightarrow r$}. |
| 1 | 15 \end{definition} |
| 16 | |
| 3 | 17 \vfill |
| 18 | |
| 19 \begin{example}[] | |
| 1 | 20 $\Sigma = \left\{ 0, 1 \right\}$. Grammatik für alle Wörter ungerader Länge, bei denen alle Nullen vor der ersten Eins stehen und weniger Nullen als Einsen vorhanden sind. |
| 3 | 21 \visible<2>{ |
| 22 \begin{align} | |
| 23 S \rightarrow 0S1 \mid S11 \mid 1 | |
| 24 \end{align} | |
| 25 } | |
| 1 | 26 \end{example} |
| 27 \end{frame} | |
| 28 } | |
| 29 | |
| 30 \defineUnit{ableitung}{% | |
| 31 \begin{frame} | |
| 32 \frametitle{Ableitungsrelation} | |
| 33 \setbeamercovered{dynamic} | |
| 34 | |
| 35 \begin{definition}[Ableitungsrelation] | |
| 3 | 36 Eine Grammatik $G$ induziert eine \structure{Ableitungsrelation} $\rightarrow_G$ auf Wörtern über $V \cup \Sigma$. Seien $x, y$ solche Wörter und |
| 37 \begin{align} | |
| 38 z &= x\alert{\alpha}y\\ | |
| 39 z^\prime &= x\alert{\beta}y\\ | |
| 40 \intertext{Dann ist} | |
| 41 z &\rightarrow_G z^\prime | |
| 42 \end{align} | |
| 43 gdw. es eine Regel $\alert{\alpha \rightarrow \beta}$ in $P$ gibt. | |
| 1 | 44 \end{definition} |
| 45 | |
| 3 | 46 \vfill |
| 47 | |
| 48 \begin{example}[] | |
| 1 | 49 Mit den Produktionen $S \rightarrow 0S1 \mid S11 \mid 1$: |
| 50 \begin{align*} | |
| 51 S &\rightarrow_G 0S1 \rightarrow_G 00S11 \rightarrow_G 00S1111 \rightarrow_G 0011111 \\ | |
| 3 | 52 \intertext{Es gilt also} |
| 53 S &\rightarrow_G^* 0011111 | |
| 1 | 54 \end{align*} |
| 55 \end{example} | |
| 56 \end{frame} | |
| 57 } | |
| 58 | |
| 3 | 59 \defineUnit{sprachtypen}{% |
| 60 \begin{frame} | |
| 61 \frametitle{Sprachtypen} | |
| 62 | |
| 63 Sei $G = (V, \Sigma, P, S)$ eine Grammatik und $\alpha \rightarrow \beta \in P$ beliebig. | |
| 64 \begin{definition}[Monotonie] | |
| 65 $G$ heißt \structure{(längen-)monoton}, wenn für $\alpha \neq S$ gilt | |
| 66 \begin{align} | |
| 67 \alert{\abs{\alpha} \leq \abs{\beta}} | |
| 68 \end{align} | |
| 69 und falls $S \to \epsilon \in P$, dann kommt $S$ nie auf der rechten Seite vor. | |
| 70 \end{definition} | |
| 71 | |
| 72 \vfill | |
| 73 | |
| 74 \begin{definition}[Chomsky-Typen] | |
| 75 Seien $A \in V$, $\gamma, \delta \in (V \cup \Sigma)^*$ und $\beta^\prime \in (V \cup \Sigma)^+$.\\ | |
| 76 Damit $G$ vom \structure{Typ k} ist, muss für $\alpha$ und $\beta$ gelten | |
| 77 \begin{center} | |
| 78 \tabulinesep=4pt | |
| 79 \begin{tabu} to .8\textwidth{X[1,c,m]|[.5pt]X[2,c,m]X[2,c,m]} | |
| 80 & $\alpha$ & $\beta$\\\tabucline[.5pt]{-} | |
| 81 \structure{Typ 0} & beliebig & beliebig\\ | |
| 82 \structure{Typ 1} & $= \alert{\gamma} A \alert{\delta}$ & $= \alert{\gamma} \beta^\prime \alert{\delta}$\\ | |
| 83 \structure{Typ 2} & $\in V$ & beliebig\\ | |
| 84 \structure{Typ 3} & $\in V$ & $\in \Sigma^+ \cup \Sigma^*V$\\ | |
| 85 \end{tabu} | |
| 86 \end{center} | |
| 87 Ab Typ 1 muss $G$ auch \alert{monoton} sein. | |
| 88 \end{definition} | |
| 89 \end{frame} | |
| 90 } | |
| 91 | |
| 1 | 92 \defineUnit{cfl}{% |
| 93 \begin{frame}[c] | |
| 94 \frametitle{Kontextfreie Sprache} | |
| 95 \setbeamercovered{dynamic} | |
| 96 | |
| 97 \begin{definition}[Kontextfreie Sprache] | |
| 98 Eine kontextfreie Grammatik $G = (V, \Sigma, P, S)$ \alert{erzeugt} die Sprache | |
| 99 \[ | |
| 100 L(G) := \left\{ w \in \Sigma^* \mid S \rightarrow_G^* w \right\} | |
| 101 \] | |
| 102 Eine Sprache $L \subseteq \Sigma^*$ heißt \alert{kontextfrei} gdw es eine kontextfreie Grammatik $G$ gibt mit $L = L(G)$. | |
| 103 \end{definition} | |
| 19 | 104 \end{frame} |
| 1 | 105 } |
| 106 | |
| 107 \defineUnit{induktivesprachdefinition}{% | |
| 108 \begin{frame} | |
| 109 \frametitle{Induktive Sprachdefinition} | |
| 110 \setbeamercovered{dynamic} | |
| 111 | |
| 112 \begin{block}{Induktive Sprachdefinition} | |
|
18
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
113 Die \alert{induktive Definition} zu einer Grammatik $G$ ergibt sich direkt aus ihren Produktionen. Dabei werden kleinere Worte zu größeren Worten \alert{zusammengesetzt}, die Definition erfolgt \structure{bottom-up}. |
| 1 | 114 \end{block} |
| 115 | |
|
18
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
116 \vfill |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
117 |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
118 \begin{example} |
| 1 | 119 Mit den Produktionen $S \rightarrow 0S1 \mid S11 \mid 1$: |
| 120 | |
| 121 \begin{align*} | |
| 122 1 &\in L_G(S) \\ | |
| 123 u \in L_G(S) \quad \Longrightarrow \quad 0\alert{u}1 &\in L_G(S) \\ | |
| 124 u \in L_G(S) \quad \Longrightarrow \quad \alert{u}11 &\in L_G(S) | |
| 125 \end{align*} | |
| 126 | |
| 127 Also z.B: | |
| 128 | |
| 129 \[ | |
| 23 | 130 1 \in L_G(S) \Longrightarrow 0\alert{1}1 \in L_G(S) \Longrightarrow \alert{011}11 \in L_G(S) |
| 1 | 131 \] |
| 132 \end{example} | |
| 133 \end{frame} | |
| 134 } | |
| 135 | |
|
10
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
136 \defineUnit{eindeutigkeit}{% |
|
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
137 \begin{frame} |
|
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
138 \frametitle{Eindeutigkeit} |
|
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
139 |
|
11
de844d67518b
fix powersets; wording
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
10
diff
changeset
|
140 \begin{definition}[kontextfreie Linksableitung] |
|
10
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
141 Eine Ableitung |
|
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
142 \begin{align} |
|
11
de844d67518b
fix powersets; wording
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
10
diff
changeset
|
143 S \to^* \structure{x}\alert{A}z \to \structure{x}\alert{\beta}z \to^* w |
|
10
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
144 \end{align} |
|
11
de844d67518b
fix powersets; wording
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
10
diff
changeset
|
145 heißt (kontextfreie) \structure{Linksableitung}, wenn für jede Anwendung jeder Produktion $\alert{A \to \beta}$ gilt, dass in \structure{$x$} kein Nichtterminal vorkommt. |
|
10
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
146 \end{definition} |
|
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
147 |
|
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
148 \vfill |
|
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
149 |
|
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
150 \begin{definition}[Eindeutigkeit] |
|
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
151 \begin{itemize} |
|
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
152 \item Eine Grammatik heißt \structure{eindeutig}, wenn es für jedes Wort genau eine Linksableitung gibt. |
|
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
153 \item Eine Sprache heißt \structure{eindeutig}, wenn es für sie eine eindeutige Grammatik gibt. |
|
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
154 \end{itemize} |
|
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
155 \end{definition} |
|
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
156 \end{frame} |
|
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
157 } |
|
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
158 |
| 1 | 159 \defineUnit{cnf}{% |
| 160 \begin{frame} | |
| 161 \frametitle{CNF} | |
| 162 \setbeamercovered{dynamic} | |
| 163 | |
| 164 \begin{definition}[Chomsky-Normalform] | |
|
16
a08f6e33cfb0
fourth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
165 Eine kontextfreie Grammatik ist in \structure{Chomsky-Normalform} (CNF) genau dann wenn alle Produktionen die Form |
| 1 | 166 \[ |
| 167 A \rightarrow \alert{a} \quad \text{oder} \quad A \rightarrow \alert{BC} | |
| 168 \] | |
| 169 haben. | |
| 170 \end{definition} | |
| 171 | |
| 172 \vfill | |
| 173 | |
| 174 \begin{theorem} | |
| 19 | 175 Zu \alert{jeder} CFG $G$ existiert eine CFG $G'$ in Chomsky-Normalform mit |
| 1 | 176 \[ |
| 177 L(G') = L(G) \alert{\setminus \left\{ \epsilon \right\}} | |
| 178 \] | |
| 179 \end{theorem} | |
| 180 \end{frame} | |
| 181 } | |
| 182 | |
| 183 \defineUnit{cnfkonstruktion}{% | |
| 184 \begin{frame} | |
| 185 \frametitle{CNF Konstruktion} | |
| 186 \setbeamercovered{dynamic} | |
| 187 | |
|
16
a08f6e33cfb0
fourth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
188 \begin{block}{CNF Konstruktion} |
| 1 | 189 Sei $G = (V, \Sigma, P, S)$ eine CFG. |
| 190 \begin{enumerate} | |
| 191 \item<1,2-> Eliminiere \alert{$\epsilon$-Produktionen} | |
| 192 \item<1,3-> Eliminiere \alert{Kettenproduktionen} | |
| 193 \item<1,4-> \alert{Ersetze Terminale} durch Nichtterminale | |
| 194 \item<1,5-> \alert{Verkürze Ketten} von Nichtterminalen der Länge $\geq 3$ | |
| 195 \end{enumerate} | |
| 196 \end{block} | |
| 197 | |
| 198 \vspace{1em} | |
| 199 | |
| 200 \only<2> { | |
| 201 Sind \alert{$B \rightarrow \epsilon$} und \alert{$A \rightarrow \alpha B \beta$} in $P$, dann füge \alert{$A \rightarrow \alpha \beta$} hinzu. Entferne danach alle $\epsilon$-Produktionen. | |
| 202 \begin{align*} | |
| 203 S &\rightarrow Ab, \quad A \rightarrow aAA \mid \epsilon \\ | |
| 204 \intertext{wird zu:} | |
| 205 S &\rightarrow \alert{Ab \mid b} \\ | |
| 206 A &\rightarrow \alert{aAA \mid aA \mid a} | |
| 207 \end{align*} | |
| 208 } | |
| 209 | |
| 210 \only<3> { | |
| 211 Sind \alert{$A \rightarrow B$} und \alert{$B \rightarrow \alpha$} in $P$, dann füge \alert{$A \rightarrow \alpha$} hinzu. Entferne danach alle Kettenproduktionen und unerreichbaren Symbole. | |
| 212 \begin{align*} | |
| 213 S &\rightarrow A, \quad A \rightarrow a \mid B, \quad B \rightarrow bS \\ | |
| 214 \intertext{wird zu:} | |
| 215 A &\rightarrow \alert{a \mid bS} \\ | |
| 216 S &\rightarrow \alert{a \mid bS} | |
| 217 \end{align*} | |
| 218 } | |
| 219 | |
| 220 \only<4> { | |
| 221 Ersetze jedes \alert{$a \in \Sigma$} in einer rechten Seite \alert{länger als $1$} durch ein neues Nichtterminal. | |
| 222 \begin{align*} | |
| 223 S &\rightarrow aa \mid Bb \mid b, \quad B \rightarrow \ldots \\ | |
| 224 \intertext{wird zu:} | |
| 225 S &\rightarrow \alert{X_aX_a \mid BX_b \mid b} \\ | |
| 226 X_a &\rightarrow \alert{a}, \quad X_b \rightarrow \alert{b} | |
| 227 \end{align*} | |
| 228 } | |
| 229 | |
| 230 \only<5> { | |
| 231 Ersetze jede Produktion der Form $A \rightarrow B_1B_2\ldots B_k$ durch neue Nichtterminale mit Produktionen der Länge $2$. | |
| 232 \begin{align*} | |
| 233 S &\rightarrow X_aX_bBX_a, \quad X_a \rightarrow a, \quad X_b \rightarrow b, \quad B \rightarrow \ldots \\ | |
| 234 \intertext{wird zu:} | |
| 235 S &\rightarrow \alert{X_aT_1} \\ | |
| 236 T_1 &\rightarrow \alert{X_bT_2}, \quad T_2 \rightarrow \alert{BX_a} \\ | |
| 237 \end{align*} | |
| 238 } | |
| 239 \end{frame} | |
| 240 } | |
| 241 | |
| 242 \defineUnit{nuetzlichessymbol}{% | |
| 243 \begin{frame} | |
| 244 \frametitle{Eigenschaften von Symbolen} | |
| 245 \setbeamercovered{dynamic} | |
| 246 | |
| 247 \begin{definition} | |
| 248 Sei $G = (V, \Sigma, P, S)$ eine CFG. \\ | |
| 249 Ein Symbol $X \in V \cup \Sigma$ ist | |
| 250 \begin{description} | |
| 251 \item[nützlich] es gibt $S \rightarrow_G^* w \in \Sigma^*$ in der X \alert{vorkommt} | |
| 252 \item[erzeugend] es gibt $\alert{X} \rightarrow_G^* w \in \Sigma^*$ | |
| 253 \item[erreichbar] es gibt $S \rightarrow_G^* \alpha \alert{X} \beta$ | |
| 254 \end{description} | |
| 255 \end{definition} | |
| 256 | |
| 257 \vfill | |
| 258 | |
| 259 \begin{theorem} | |
| 260 Nützliche Symbole \alert{sind} erzeugend und erreichbar. Aber \alert{nicht} notwendigerweise umgekehrt. | |
| 261 \[ | |
| 262 S \rightarrow AB \mid a, \quad A \rightarrow b | |
| 263 \] | |
| 264 \end{theorem} | |
| 265 \end{frame} | |
| 266 } | |
| 267 | |
| 268 \defineUnit{cfpl}{% | |
| 269 \begin{frame} | |
| 270 \frametitle{Pumping Lemma für CFLs} | |
| 271 \setbeamercovered{dynamic} | |
| 272 | |
| 273 \begin{theorem}[Pumping Lemma für kontextfreie Sprachen] | |
|
16
a08f6e33cfb0
fourth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
274 Sei $L \subseteq \Sigma^*$ kontextfrei.\\ |
|
a08f6e33cfb0
fourth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
275 Dann gibt es ein $n > 0$, so dass sich \alert{jedes} $z \in L$ mit $|z| \geq n$ so in \alert{$z = uvwxy$} zerlegen lässt, dass |
| 1 | 276 \begin{itemize} |
| 277 \item $vx \alert{\neq \epsilon}$ | |
| 278 \item $|vwx| \alert{\leq n}$ | |
| 279 \item $\forall i \alert{\geq 0}. uv^iwx^iy \in L$ | |
| 280 \end{itemize} | |
| 281 \end{theorem} | |
| 282 | |
| 283 \vfill | |
| 284 | |
|
17
0f7daeda8363
wording; add explicit productions to cf-pumping lemma
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
16
diff
changeset
|
285 \vspace{1.5em} |
| 1 | 286 \begin{center} |
| 287 \begin{columns} | |
| 288 \begin{column}{.4\textwidth} | |
| 289 \begin{tikzpicture} | |
| 290 \coordinate (outer) at (2, 2.4); | |
| 291 \coordinate (middle) at (2.2, 1.2); | |
| 292 \coordinate (inner) at (2.2, 0.6); | |
| 293 % outer | |
| 294 \draw[fill=tumred!40] (0, 0) -- (1.2, 0) -- (middle) -- (3.2, 0) -- (4, 0) -- (outer) node[above] {$S$} -- (0, 0); | |
| 295 % middle | |
| 296 \draw[fill=tumgreen!40] (1.2, 0) -- (1.7, 0) -- (inner) -- (2.7, 0) -- (3.2, 0) -- (middle) -- (1.2, 0); | |
| 297 % inner | |
| 298 \draw[fill=tumblue!40] (1.7, 0) -- (inner) -- (2.7, 0) -- (1.7, 0); | |
| 299 | |
| 300 % path | |
| 301 \draw[dashed, thick] (outer) -- (middle) -- (inner); | |
| 302 \draw[fill] (outer) circle (1pt); | |
| 303 \draw[fill] (middle) circle (1pt); | |
| 304 \draw[fill] (inner) circle (1pt); | |
| 305 | |
| 306 % nodes | |
| 307 \node[below] at (0.6, 0) {$u$}; | |
| 308 \node[below] at (1.45, 0) {$v$}; | |
| 309 \node[below] at (2.2, 0) {$w$}; | |
| 310 \node[below] at (2.95, 0) {$x$}; | |
| 311 \node[below] at (3.6, 0) {$y$}; | |
|
17
0f7daeda8363
wording; add explicit productions to cf-pumping lemma
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
16
diff
changeset
|
312 |
|
0f7daeda8363
wording; add explicit productions to cf-pumping lemma
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
16
diff
changeset
|
313 \node[right] at (middle) {$A$}; |
|
0f7daeda8363
wording; add explicit productions to cf-pumping lemma
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
16
diff
changeset
|
314 \node[right] at (inner) {$A$}; |
|
0f7daeda8363
wording; add explicit productions to cf-pumping lemma
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
16
diff
changeset
|
315 |
|
0f7daeda8363
wording; add explicit productions to cf-pumping lemma
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
16
diff
changeset
|
316 \node at (2, 3.4) {$S \to^* uAy \to^* uvAxy \to^* uvwxy$}; |
| 1 | 317 \end{tikzpicture} |
| 318 \end{column} | |
| 319 \begin{column}{.4\textwidth} | |
| 320 \begin{tikzpicture} | |
| 321 \coordinate (outer) at (2, 2.4); | |
| 322 \coordinate (middle) at (2.2, 1.2); | |
| 323 \coordinate (inner) at (2.2, 0.6); | |
| 324 % outer | |
| 325 \draw[fill=tumred!40] (0, 0) -- (1.2, 0) -- (middle) -- (3.2, 0) -- (4, 0) -- (outer) node[above] {$S$} -- (0, 0); | |
| 326 % inner | |
| 327 \draw[fill=tumblue!40] (1.7, 0.6) -- (middle) -- (2.7, 0.6) -- (1.7, 0.6); | |
| 328 | |
| 329 % path | |
| 330 \draw[dashed, thick] (outer) -- (middle); | |
| 331 \draw[fill] (outer) circle (1pt); | |
| 332 \draw[fill] (middle) circle (1pt); | |
| 333 | |
| 334 % nodes | |
| 335 \node[below] at (0.6, 0) {$u$}; | |
| 336 \node[below] at (2.2, 0) {$w$}; | |
| 337 \node[below] at (3.6, 0) {$y$}; | |
|
17
0f7daeda8363
wording; add explicit productions to cf-pumping lemma
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
16
diff
changeset
|
338 |
|
0f7daeda8363
wording; add explicit productions to cf-pumping lemma
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
16
diff
changeset
|
339 \node[right] at (middle) {$A$}; |
|
0f7daeda8363
wording; add explicit productions to cf-pumping lemma
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
16
diff
changeset
|
340 |
|
0f7daeda8363
wording; add explicit productions to cf-pumping lemma
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
16
diff
changeset
|
341 \node at (2, 3.4) {$S \to^* uAy \to^* uwy$}; |
| 1 | 342 \end{tikzpicture} |
| 343 \end{column} | |
| 344 \end{columns} | |
| 345 \end{center} | |
| 346 \end{frame} | |
| 347 } | |
| 348 | |
|
18
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
349 \defineUnit{ogden}{% |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
350 \begin{frame} |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
351 \frametitle{Ogden Lemma für kontextfreie Sprachen} |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
352 \setbeamercovered{dynamic} |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
353 |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
354 \begin{theorem}[Ogden Lemma für kontextfreie Sprachen] |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
355 Sei $L \subseteq \Sigma^*$ kontextfrei.\\ |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
356 Dann gibt es ein $n > 0$, so dass für \alert{jedes} $z \in L$ mit $|z| \geq n$ gilt:\\ |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
357 Für \alert{jede} Markierung $M$ von \alert{mindestens $n$} Buchstaben in $z$ gibt es eine Zerlegung $z = uvwxy$ mit |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
358 \begin{itemize} |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
359 \item $|vx|_M \alert{\geq 1}$ |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
360 \item $|vwx|_M \alert{\leq n}$ |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
361 \item $\forall i \alert{\geq 0}. uv^iwx^iy \in L$ |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
362 \end{itemize} |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
363 \end{theorem} |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
364 |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
365 \hfill |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
366 |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
367 \begin{example}[Markierung] |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
368 Sei $w = abaabaaa$ ein Wort. Dann ist |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
369 \begin{align} |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
370 w = a\structure{ba}a\structure{b}aaa |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
371 \end{align} |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
372 eine Markierung mit $|w|_M = 3$. |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
373 \end{example} |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
374 \end{frame} |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
375 } |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
376 |
| 1 | 377 \defineUnit{cyk}{% |
| 378 \begin{frame} | |
| 379 \frametitle{CYK} | |
| 380 \setbeamercovered{dynamic} | |
| 381 | |
| 382 \begin{definition}[Cocke-Younger-Kasami-Algorithmus] | |
|
16
a08f6e33cfb0
fourth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
383 Der \structure{CYK-Algorithmus} entscheidet das Wortproblem für kontextfreie Grammatiken in Chomsky-Normalform in $\Oh(n^3)$. \\ |
| 1 | 384 Gegeben eine \alert{Grammatik} $G = (V, \Sigma, P, S)$ in CNF und ein \alert{Wort} $w = a_1 \ldots a_n \in \Sigma^*$. |
| 385 Mit \[ V_{ij} := \left\{ A \in V \mid A \rightarrow_G^* \alert{a_i \ldots a_j} \right\}\] | |
| 386 ist \[ w \in L(G) \Leftrightarrow S \in V_{\alert{1n}} \] | |
| 387 \end{definition} | |
| 388 | |
| 389 \begin{align*} | |
| 390 V_{ii} &= \left\{ A \in V \mid (A \rightarrow a_i) \in P \right\} \\ | |
| 391 V_{ij} &= \left\{ A \in V \mid \exists k, B \in V_{ik}, C \in V_{k+1,j} \;.\; (A \rightarrow BC) \in P \right\} | |
| 392 \end{align*} | |
| 19 | 393 \end{frame} |
| 1 | 394 } |
| 395 | |
| 396 \defineUnit{cykbeispiel}{% | |
| 397 \begin{frame} | |
| 398 \frametitle{CYK} | |
| 399 \setbeamercovered{dynamic} | |
| 400 | |
|
16
a08f6e33cfb0
fourth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
401 \begin{block}{CYK-Algorithmus} |
| 1 | 402 Kombiniere \alert{Teilwörter} zum ganzen Wort, wenn möglich. |
| 403 \begin{enumerate} | |
| 404 \item Initialisiere mit den \alert{$V_{ii}$}. | |
| 405 \item<3-5> Befülle die Tabelle von unten nach oben. | |
| 406 \end{enumerate} | |
| 407 \end{block} | |
| 408 | |
| 409 \[ S \rightarrow AB \mid BC, \quad A \rightarrow BA \mid a, \quad B \rightarrow CC \mid b, \quad C \rightarrow AB \mid a \] | |
|
16
a08f6e33cfb0
fourth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
410 \vspace{2em} |
| 1 | 411 \begin{center} |
| 412 \extrarowsep=5pt | |
| 413 \begin{tabu}to .8\textwidth{r|X[c]|X[c]|X[c]|X[c]|} | |
| 414 \tabucline{2-2} | |
| 415 4 & \alt<-4>{}{$S,\ldots$} \\ \tabucline{2-3} | |
| 416 3 & \alt<-3>{}{$\emptyset$} & \alt<-3>{}{$S, A, C$} \\ \tabucline{2-4} | |
| 20 | 417 2 & \alt<-2>{}{$A,S$} & \alt<-2>{}{$B$} & \alt<-2>{}{$B$} \\ \tabucline{2-5} |
| 1 | 418 1 & \alt<-1>{}{$B$} & \alt<1>{}{$A,C$} & \alt<1>{}{$A,C$} & \alt<1>{}{$A,C$} \\ \tabucline{2-5} |
| 419 \multicolumn{1}{r}{} & \multicolumn{1}{c}{\alert{b}} & \multicolumn{1}{c}{\alert{a}} & \multicolumn{1}{c}{\alert{a}} & \multicolumn{1}{c}{\alert{a}} \\ | |
| 420 \end{tabu} | |
| 421 \end{center} | |
| 422 \end{frame} | |
| 423 } | |
| 424 | |
|
18
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
425 \defineUnit{greibach}{% |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
426 \begin{frame} |
|
21
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
427 \frametitle{Greibach-Normalform} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
428 |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
429 \begin{definition}[Greibach-Normalform] |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
430 Eine kontextfreie Grammatik ist in \structure{Greibach-Normalform} (GNF) genau dann wenn alle Produktionen außer $S \to \epsilon$ die Form |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
431 \[ |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
432 A \rightarrow \alert{a\alpha} \quad \text{mit} \quad a \in \Sigma, \alpha \in V^* |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
433 \] |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
434 haben. |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
435 \end{definition} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
436 |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
437 \vfill |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
438 |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
439 \begin{theorem} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
440 Zu \alert{jeder} CFG $G$ existiert eine CFG $G'$ in Greibach-Normalform mit |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
441 \[ |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
442 L(G') = L(G) |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
443 \] |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
444 \end{theorem} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
445 \end{frame} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
446 |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
447 \begin{frame} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
448 \frametitle{Einsetzen von Produktionen} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
449 |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
450 \begin{theorem}[Einsetzen von Produktionen] |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
451 Enthält eine CFG die Produktionen |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
452 \begin{align} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
453 A &\to \alpha_1 \structure{B} \alpha_2\\ |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
454 \structure{B} &\to \alert{\beta_1} \mid \dots \mid \alert{\beta_k} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
455 \intertext{so ändert sich die erzeugte Sprache nicht, wenn man $B$ in $A$ \structure{einsetzt}.} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
456 A &\to \alpha_1 \alert{\beta_1} \alpha_2 \mid \dots \mid \alpha_1 \alert{\beta_k} \alpha_2 |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
457 \end{align} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
458 \end{theorem} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
459 |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
460 \vfill |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
461 |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
462 \begin{example} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
463 Die Grammatik |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
464 \begin{align} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
465 S &\to a \mid a\structure{B}c \\ |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
466 \structure{B} &\to \alert{b} \mid \alert{bS} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
467 \intertext{ist äquivalent zur Grammatik} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
468 S &\to a \mid a\alert{b}c \mid a\alert{bS}c |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
469 \end{align} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
470 \end{example} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
471 \end{frame} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
472 |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
473 \begin{frame} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
474 \frametitle{Linksrekursive Produktionen} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
475 |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
476 \begin{definition}[Linksrekursive Produktion] |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
477 Man nennt eine Produktion \structure{linksrekursiv}, wenn sie die Form |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
478 \[ |
|
22
334369297f54
fix compilation error; fix errors in gnf construction; start suppliing complete notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
21
diff
changeset
|
479 \structure{A} \to \structure{A}\alpha_1 \mid \dots \mid \structure{A}\alpha_k \mid \beta_1 \mid \dots \mid \beta_l \quad \text{mit} \quad \alpha_i, \beta_i \in \left( V \cup \Sigma \right)^+ |
|
21
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
480 \] |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
481 hat, wobei die $\beta_i$ nicht mit $A$ beginnen. |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
482 \end{definition} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
483 |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
484 \vfill |
|
18
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
485 |
|
21
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
486 \begin{theorem}[Ersetzen von linksrekursiven Produktionen] |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
487 Sei $A$ eine linksrekursive Produktion einer CFG.\\ |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
488 Dann ändert sich die erzeugte Sprache nicht, wenn wir $A$ \structure{ersetzen} durch |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
489 \begin{align} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
490 \structure{A} &\to \beta_1 \mid \dots \mid \beta_l \mid \beta_1 \alert{B} \mid \dots \mid \beta_l \alert{B}\\ |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
491 \alert{B} &\to \alpha_1 \mid \dots \mid \alpha_k \mid \alpha_1 \alert{B} \mid \dots \mid \alpha_k \alert{B} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
492 \end{align} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
493 \alert{$B$} ist niemals linksrekursiv. |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
494 \end{theorem} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
495 \end{frame} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
496 } |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
497 |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
498 \defineUnit{greibachkonstruktion}{% |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
499 \begin{frame} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
500 \frametitle{GNF Konstruktion} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
501 |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
502 \begin{block}{GNF Konstruktion} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
503 Sei $G = (V, \Sigma, P, S)$ eine CFG. |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
504 \begin{enumerate} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
505 \item<1,2-> \alert{Nummeriere} Nichtterminale |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
506 \item<1,3-> Mache Prduktionen \alert{aufsteigend} und \alert{nicht rekursiv} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
507 \item<1,5-> \alert{Setze} Produktionen absteigend \alert{ein} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
508 \end{enumerate} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
509 \end{block} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
510 |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
511 \vspace{1em} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
512 |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
513 \only<2> { |
|
22
334369297f54
fix compilation error; fix errors in gnf construction; start suppliing complete notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
21
diff
changeset
|
514 Benenne alle Nichtterminale \structure{beliebig} um in $A_1, \dots, A_{\abs{V}}$. |
|
21
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
515 \begin{align} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
516 S &\rightarrow Ab, \quad A \rightarrow aAS \mid \epsilon \\ |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
517 \intertext{wird zu} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
518 A_1 &\to A_2b\\ |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
519 A_2 &\to aA_2A_1 |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
520 \end{align} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
521 } |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
522 |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
523 \only<3,4> { |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
524 Betrachte alle Produktionen $A_l \to \dots$ in \structure{aufsteigender Reihenfolge}.\\ |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
525 \begin{itemize} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
526 \item Existieren Produktionen der Form $A_l \to \structure{A_r}\alpha$ mit \alert{$r < l$}, dann setze \structure{$A_r$} in $A_l$ ein. |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
527 \only<3> { |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
528 \begin{align} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
529 A_1 &\to A_2 \mid a \mid b \\ |
|
22
334369297f54
fix compilation error; fix errors in gnf construction; start suppliing complete notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
21
diff
changeset
|
530 A_2 &\to \structure{A_1}A_1 |
|
21
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
531 \intertext{wird zu} |
|
24
322b0166cc24
fix errors in GNF and pda
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
23
diff
changeset
|
532 A_1 &\to A_2 \mid a \mid b\\ |
|
22
334369297f54
fix compilation error; fix errors in gnf construction; start suppliing complete notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
21
diff
changeset
|
533 A_2 &\to \structure{A_2}A_1 \mid \structure{a}A_1 \mid \structure{b}A_1 |
|
21
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
534 \end{align} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
535 } |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
536 \item Entferne danach alle \structure{linksrekursiven} $A_l$-Produktionen. |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
537 \only<4> { |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
538 \begin{align} |
|
22
334369297f54
fix compilation error; fix errors in gnf construction; start suppliing complete notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
21
diff
changeset
|
539 A_2 &\to A_2\structure{A_1} \mid \alert{aA_1} \mid \alert{bA_1} |
|
21
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
540 \intertext{wird zu} |
|
22
334369297f54
fix compilation error; fix errors in gnf construction; start suppliing complete notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
21
diff
changeset
|
541 A_2 &\to \alert{aA_1} \mid \alert{bA_1} \mid \alert{aA_1}A_3 \mid \alert{bA_1}A_3\\ |
|
334369297f54
fix compilation error; fix errors in gnf construction; start suppliing complete notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
21
diff
changeset
|
542 A_3 &\to \structure{A_1} \mid \structure{A_1}A_3 |
|
21
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
543 \end{align} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
544 } |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
545 \end{itemize} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
546 } |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
547 |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
548 \only<5> { |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
549 Betrachte alle Produktionen $A_l \to \dots$ in \structure{absteigender Reihenfolge}.\\ |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
550 \begin{itemize} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
551 \item Existieren Produktionen der Form $A_l \to \structure{A_r}\alpha$ mit \alert{$r > l$}, dann setze \structure{$A_r$} in $A_l$ ein. |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
552 \begin{align} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
553 A_1 &\to a \mid b \mid \structure{A_2} \\ |
|
22
334369297f54
fix compilation error; fix errors in gnf construction; start suppliing complete notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
21
diff
changeset
|
554 A_2 &\to aA_1 \mid bA_1 \mid aA_1A_3 \mid bA_1A_3\\ |
|
334369297f54
fix compilation error; fix errors in gnf construction; start suppliing complete notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
21
diff
changeset
|
555 A_3 &\to bA_3 \mid c |
|
21
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
556 \intertext{$A_1$ wird zu} |
|
22
334369297f54
fix compilation error; fix errors in gnf construction; start suppliing complete notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
21
diff
changeset
|
557 A_1 &\to a \mid b \mid \structure{aA_1} \mid \structure{bA_1} \mid \structure{aA_1A_3} \mid \structure{bA_1A_3} |
|
21
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
558 \end{align} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
559 \end{itemize} |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
560 |
|
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
561 } |
|
18
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
562 \end{frame} |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
563 } |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
564 |
| 1 | 565 \defineUnit{pda}{% |
| 566 \begin{frame} | |
| 567 \frametitle{Kellerautomaten} | |
| 568 \setbeamercovered{dynamic} | |
| 569 | |
| 570 \begin{definition}[Kellerautomat] | |
|
18
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
571 Ein \structure{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem |
| 1 | 572 \begin{itemize} |
|
18
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
573 \item endlichen Menge von \structure{Zuständen} $Q$ |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
574 \item endlichen \structure{Eingabealphabet} $\Sigma$ |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
575 \item endlichen \structure{Kelleralphabet} $\Gamma$ |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
576 \item \structure{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$ |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
577 \item \structure{Startzustand} $q_0 \in Q$ |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
578 \item \structure{Kellerinitialisierung} $Z_0 \in \Gamma$ |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
579 \item Menge von \structure{Endzuständen} $F \subseteq Q$ |
| 1 | 580 \end{itemize} |
| 581 \end{definition} | |
| 582 | |
|
18
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
583 \vfill |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
584 |
| 1 | 585 \begin{center} |
| 586 \begin{tikzpicture}[automaton, node distance=4cm] | |
| 587 \node[state] (q0) {$q_i$}; | |
| 588 \node[state] (q1) [right of = q0] {$q_j$}; | |
| 589 | |
| 590 \draw[every edge] (q0) edge node {$a, X/\gamma$} (q1); | |
| 591 \end{tikzpicture} | |
| 592 \end{center} | |
| 593 \end{frame} | |
| 594 } | |
| 595 | |
| 596 \defineUnit{pdaakzeptanz}{% | |
| 597 \begin{frame} | |
| 598 \frametitle{Kellerautomaten} | |
| 599 \setbeamercovered{dynamic} | |
| 600 | |
| 601 \begin{definition}[Kellerautomat] | |
|
18
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
602 Ein \structure{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem |
| 1 | 603 \begin{itemize} |
|
18
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
604 \item \structure{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$ |
| 1 | 605 \end{itemize} |
| 606 \end{definition} | |
| 607 | |
| 608 \vfill | |
| 609 | |
| 610 \begin{definition}[Akzeptanz] | |
|
18
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
611 Ein PDA $P$ akzeptiert $w \in \Sigma^*$ \structure{mit Endzustand} gdw |
| 1 | 612 \[ \exists \alert{f \in F}, \gamma \in \Gamma^*.(q_0, w, Z_0) \rightarrow_P^* (\alert{f}, \epsilon, \gamma) \] |
|
18
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
613 Ein PDA $P$ akzeptiert $w \in \Sigma^*$ \structure{mit leerem Keller} gdw |
| 1 | 614 \[ \exists q \in Q.(q_0, w, Z_0) \rightarrow_P^* (q, \epsilon, \alert{\epsilon}) \] |
| 615 \end{definition} | |
| 616 \end{frame} | |
| 617 } | |
| 618 | |
| 619 \defineUnit{pdabeispiel}{% | |
| 620 \begin{frame} | |
| 621 \frametitle{Kellerautomaten} | |
| 622 \setbeamercovered{dynamic} | |
| 623 | |
| 624 \begin{definition}[Kellerautomat] | |
|
18
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
625 Ein \structure{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem |
| 1 | 626 \begin{itemize} |
| 627 | |
|
18
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
628 \item \structure{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$ |
| 1 | 629 \end{itemize} |
| 630 \end{definition} | |
| 631 | |
| 632 \vfill | |
| 633 | |
| 634 \begin{example}[] | |
|
18
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
635 PDA akzeptierend \alert{mit leerem Keller} zu $L = \left\{ a^nb^n \mid n \in \N_0 \right\}$. |
| 1 | 636 |
|
18
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
637 \bigskip |
| 1 | 638 \centering |
| 639 \begin{tikzpicture}[automaton] | |
| 640 | |
| 641 \node[state, initial] (q0) {$q_0$}; | |
| 642 \node[state] (q1) [right of = q0] {$q_1$}; | |
|
18
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
643 \node[state] (q2) [right of = q1] {$q_2$}; |
| 1 | 644 |
|
21
6a3cdddedcf7
fifth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
20
diff
changeset
|
645 \draw[->] (q0) edge [loop above] node {$\epsilon, Z_0/\epsilon$} (q0); |
| 1 | 646 |
|
18
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
647 \draw[->] (q0) edge node {$a, Z_0/AZ_0$} (q1); |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
648 \draw[->] (q1) edge node {$\epsilon, A/A$} (q2); |
| 1 | 649 |
|
18
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
650 \draw[->] (q1) edge [loop above] node {$a, */A*$} (q1); |
|
1359f5a6aa60
first half of fifth notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
17
diff
changeset
|
651 |
|
24
322b0166cc24
fix errors in GNF and pda
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
23
diff
changeset
|
652 \draw[->] (q2) edge [loop above] node {$b, A/\epsilon$} (q2); |
|
322b0166cc24
fix errors in GNF and pda
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
23
diff
changeset
|
653 \draw[->] (q2) edge [loop below] node {$\epsilon, Z_0/\epsilon$} (q2); |
| 1 | 654 \end{tikzpicture} |
| 655 \end{example} | |
| 656 \end{frame} | |
| 657 } | |
| 658 | |
| 659 \defineUnit{kontextfreiesprachen}{% | |
| 660 \begin{frame} | |
| 661 \frametitle{Kontextfreie Sprachen} | |
| 662 \setbeamercovered{dynamic} | |
| 663 | |
| 664 \begin{center} | |
| 665 \begin{tikzpicture}[node distance=3cm] | |
| 666 \node (CFG) {CFG}; | |
| 667 \node (CNF) [right of = CFG] {CNF}; | |
| 668 \node (PDAe) [right of = CNF] {PDA$_\epsilon$}; | |
| 669 \node (PDAf) [right of = PDAe] {PDA$_F$}; | |
| 670 | |
| 671 \draw [every edge, <->] (CFG) -- (CNF); | |
| 672 \draw [every edge, <->] (CNF) -- (PDAe); | |
| 673 \draw [every edge, <->] (PDAe) -- (PDAf); | |
| 674 \end{tikzpicture} | |
| 675 \end{center} | |
| 676 | |
| 677 \vfill | |
| 678 | |
| 679 \begin{itemize} | |
| 680 \item \alert{Abschlusseigenschaften} | |
| 681 \end{itemize} | |
| 682 \begin{table} | |
| 683 \begin{tabu}to \textwidth{X[c]|ccccc} | |
| 684 & Schnitt & Vereinigung & Komplement & Produkt & Stern \\ \tabucline{} | |
| 685 REG & ja & ja & ja & ja & ja\\ | |
| 19 | 686 CFL & nein & ja & nein & ja & ja |
| 1 | 687 \end{tabu} |
| 688 \end{table} | |
| 689 | |
| 690 \begin{itemize} | |
| 691 \item \alert{Entscheidbarkeit} | |
| 692 \end{itemize} | |
| 693 \begin{table} | |
| 694 \begin{tabu}to \textwidth{X[c]|cccc} | |
| 695 & Wortproblem & Leerheit & Äquivalenz & Schnittproblem\\ \tabucline{} | |
| 696 DFA & $\Oh(n)$ & ja & ja & ja \\ | |
| 697 CFG & $\Oh(n^3)$ & ja & nein & nein | |
| 698 \end{tabu} | |
| 699 \end{table} | |
| 700 \end{frame} | |
| 701 } |