Mercurial > 14ss.theoinf
annotate notes/tex/grammars.tex @ 16:a08f6e33cfb0
fourth sheet and notes
author | Markus Kaiser <markus.kaiser@in.tum.de> |
---|---|
date | Sat, 10 May 2014 19:39:01 +0200 |
parents | de844d67518b |
children | 0f7daeda8363 |
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} | |
104 \end{frame} | |
105 } | |
106 | |
107 \defineUnit{induktivesprachdefinition}{% | |
108 \begin{frame} | |
109 \frametitle{Induktive Sprachdefinition} | |
110 \setbeamercovered{dynamic} | |
111 | |
112 \begin{block}{Induktive Sprachdefinition} | |
113 Die \alert{induktive Definition} ($\Longrightarrow$) erzeugt Wörter \alert{bottom-up}, setzt also kleine Wörter zu größeren zusammen. | |
114 \end{block} | |
115 | |
116 \begin{example}[Vorbereitung 3] | |
117 Mit den Produktionen $S \rightarrow 0S1 \mid S11 \mid 1$: | |
118 | |
119 \begin{align*} | |
120 1 &\in L_G(S) \\ | |
121 u \in L_G(S) \quad \Longrightarrow \quad 0\alert{u}1 &\in L_G(S) \\ | |
122 u \in L_G(S) \quad \Longrightarrow \quad \alert{u}11 &\in L_G(S) | |
123 \end{align*} | |
124 | |
125 Also z.B: | |
126 | |
127 \[ | |
128 1 \in L_G(S) \Longrightarrow 0\alert{1}0 \in L_G(S) \Longrightarrow \alert{010}11 \in L_G(S) | |
129 \] | |
130 \end{example} | |
131 \end{frame} | |
132 } | |
133 | |
10
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
134 \defineUnit{eindeutigkeit}{% |
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
135 \begin{frame} |
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
136 \frametitle{Eindeutigkeit} |
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
137 |
11
de844d67518b
fix powersets; wording
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
10
diff
changeset
|
138 \begin{definition}[kontextfreie Linksableitung] |
10
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
139 Eine Ableitung |
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
140 \begin{align} |
11
de844d67518b
fix powersets; wording
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
10
diff
changeset
|
141 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
|
142 \end{align} |
11
de844d67518b
fix powersets; wording
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
10
diff
changeset
|
143 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
|
144 \end{definition} |
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
145 |
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
146 \vfill |
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 \begin{definition}[Eindeutigkeit] |
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
149 \begin{itemize} |
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
150 \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
|
151 \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
|
152 \end{itemize} |
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
153 \end{definition} |
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
154 \end{frame} |
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
155 } |
e1b3b7b99d28
second notes and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
156 |
1 | 157 \defineUnit{cnf}{% |
158 \begin{frame} | |
159 \frametitle{CNF} | |
160 \setbeamercovered{dynamic} | |
161 | |
162 \begin{definition}[Chomsky-Normalform] | |
16
a08f6e33cfb0
fourth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
163 Eine kontextfreie Grammatik ist in \structure{Chomsky-Normalform} (CNF) genau dann wenn alle Produktionen die Form |
1 | 164 \[ |
165 A \rightarrow \alert{a} \quad \text{oder} \quad A \rightarrow \alert{BC} | |
166 \] | |
167 haben. | |
168 \end{definition} | |
169 | |
170 \vfill | |
171 | |
172 \begin{theorem} | |
173 Zu \alert{jeder} CFG $G$ existiert eine CFG $G'$ in Chomsky-Normalform mit | |
174 \[ | |
175 L(G') = L(G) \alert{\setminus \left\{ \epsilon \right\}} | |
176 \] | |
177 \end{theorem} | |
178 \end{frame} | |
179 } | |
180 | |
181 \defineUnit{cnfkonstruktion}{% | |
182 \begin{frame} | |
183 \frametitle{CNF Konstruktion} | |
184 \setbeamercovered{dynamic} | |
185 | |
16
a08f6e33cfb0
fourth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
186 \begin{block}{CNF Konstruktion} |
1 | 187 Sei $G = (V, \Sigma, P, S)$ eine CFG. |
188 \begin{enumerate} | |
189 \item<1,2-> Eliminiere \alert{$\epsilon$-Produktionen} | |
190 \item<1,3-> Eliminiere \alert{Kettenproduktionen} | |
191 \item<1,4-> \alert{Ersetze Terminale} durch Nichtterminale | |
192 \item<1,5-> \alert{Verkürze Ketten} von Nichtterminalen der Länge $\geq 3$ | |
193 \end{enumerate} | |
194 \end{block} | |
195 | |
196 \vspace{1em} | |
197 | |
198 \only<2> { | |
199 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. | |
200 \begin{align*} | |
201 S &\rightarrow Ab, \quad A \rightarrow aAA \mid \epsilon \\ | |
202 \intertext{wird zu:} | |
203 S &\rightarrow \alert{Ab \mid b} \\ | |
204 A &\rightarrow \alert{aAA \mid aA \mid a} | |
205 \end{align*} | |
206 } | |
207 | |
208 \only<3> { | |
209 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. | |
210 \begin{align*} | |
211 S &\rightarrow A, \quad A \rightarrow a \mid B, \quad B \rightarrow bS \\ | |
212 \intertext{wird zu:} | |
213 A &\rightarrow \alert{a \mid bS} \\ | |
214 S &\rightarrow \alert{a \mid bS} | |
215 \end{align*} | |
216 } | |
217 | |
218 \only<4> { | |
219 Ersetze jedes \alert{$a \in \Sigma$} in einer rechten Seite \alert{länger als $1$} durch ein neues Nichtterminal. | |
220 \begin{align*} | |
221 S &\rightarrow aa \mid Bb \mid b, \quad B \rightarrow \ldots \\ | |
222 \intertext{wird zu:} | |
223 S &\rightarrow \alert{X_aX_a \mid BX_b \mid b} \\ | |
224 X_a &\rightarrow \alert{a}, \quad X_b \rightarrow \alert{b} | |
225 \end{align*} | |
226 } | |
227 | |
228 \only<5> { | |
229 Ersetze jede Produktion der Form $A \rightarrow B_1B_2\ldots B_k$ durch neue Nichtterminale mit Produktionen der Länge $2$. | |
230 \begin{align*} | |
231 S &\rightarrow X_aX_bBX_a, \quad X_a \rightarrow a, \quad X_b \rightarrow b, \quad B \rightarrow \ldots \\ | |
232 \intertext{wird zu:} | |
233 S &\rightarrow \alert{X_aT_1} \\ | |
234 T_1 &\rightarrow \alert{X_bT_2}, \quad T_2 \rightarrow \alert{BX_a} \\ | |
235 \end{align*} | |
236 } | |
237 \end{frame} | |
238 } | |
239 | |
240 \defineUnit{nuetzlichessymbol}{% | |
241 \begin{frame} | |
242 \frametitle{Eigenschaften von Symbolen} | |
243 \setbeamercovered{dynamic} | |
244 | |
245 \begin{definition} | |
246 Sei $G = (V, \Sigma, P, S)$ eine CFG. \\ | |
247 Ein Symbol $X \in V \cup \Sigma$ ist | |
248 \begin{description} | |
249 \item[nützlich] es gibt $S \rightarrow_G^* w \in \Sigma^*$ in der X \alert{vorkommt} | |
250 \item[erzeugend] es gibt $\alert{X} \rightarrow_G^* w \in \Sigma^*$ | |
251 \item[erreichbar] es gibt $S \rightarrow_G^* \alpha \alert{X} \beta$ | |
252 \end{description} | |
253 \end{definition} | |
254 | |
255 \vfill | |
256 | |
257 \begin{theorem} | |
258 Nützliche Symbole \alert{sind} erzeugend und erreichbar. Aber \alert{nicht} notwendigerweise umgekehrt. | |
259 \[ | |
260 S \rightarrow AB \mid a, \quad A \rightarrow b | |
261 \] | |
262 \end{theorem} | |
263 \end{frame} | |
264 } | |
265 | |
266 \defineUnit{cfpl}{% | |
267 \begin{frame} | |
268 \frametitle{Pumping Lemma für CFLs} | |
269 \setbeamercovered{dynamic} | |
270 | |
271 \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
|
272 Sei $L \subseteq \Sigma^*$ kontextfrei.\\ |
a08f6e33cfb0
fourth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
273 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 | 274 \begin{itemize} |
275 \item $vx \alert{\neq \epsilon}$ | |
276 \item $|vwx| \alert{\leq n}$ | |
277 \item $\forall i \alert{\geq 0}. uv^iwx^iy \in L$ | |
278 \end{itemize} | |
279 \end{theorem} | |
280 | |
281 \vfill | |
282 | |
283 \begin{center} | |
284 \begin{columns} | |
285 \begin{column}{.4\textwidth} | |
286 \begin{tikzpicture} | |
287 \coordinate (outer) at (2, 2.4); | |
288 \coordinate (middle) at (2.2, 1.2); | |
289 \coordinate (inner) at (2.2, 0.6); | |
290 % outer | |
291 \draw[fill=tumred!40] (0, 0) -- (1.2, 0) -- (middle) -- (3.2, 0) -- (4, 0) -- (outer) node[above] {$S$} -- (0, 0); | |
292 % middle | |
293 \draw[fill=tumgreen!40] (1.2, 0) -- (1.7, 0) -- (inner) -- (2.7, 0) -- (3.2, 0) -- (middle) -- (1.2, 0); | |
294 % inner | |
295 \draw[fill=tumblue!40] (1.7, 0) -- (inner) -- (2.7, 0) -- (1.7, 0); | |
296 | |
297 % path | |
298 \draw[dashed, thick] (outer) -- (middle) -- (inner); | |
299 \draw[fill] (outer) circle (1pt); | |
300 \draw[fill] (middle) circle (1pt); | |
301 \draw[fill] (inner) circle (1pt); | |
302 | |
303 % nodes | |
304 \node[below] at (0.6, 0) {$u$}; | |
305 \node[below] at (1.45, 0) {$v$}; | |
306 \node[below] at (2.2, 0) {$w$}; | |
307 \node[below] at (2.95, 0) {$x$}; | |
308 \node[below] at (3.6, 0) {$y$}; | |
309 \end{tikzpicture} | |
310 \end{column} | |
311 \begin{column}{.4\textwidth} | |
312 \begin{tikzpicture} | |
313 \coordinate (outer) at (2, 2.4); | |
314 \coordinate (middle) at (2.2, 1.2); | |
315 \coordinate (inner) at (2.2, 0.6); | |
316 % outer | |
317 \draw[fill=tumred!40] (0, 0) -- (1.2, 0) -- (middle) -- (3.2, 0) -- (4, 0) -- (outer) node[above] {$S$} -- (0, 0); | |
318 % inner | |
319 \draw[fill=tumblue!40] (1.7, 0.6) -- (middle) -- (2.7, 0.6) -- (1.7, 0.6); | |
320 | |
321 % path | |
322 \draw[dashed, thick] (outer) -- (middle); | |
323 \draw[fill] (outer) circle (1pt); | |
324 \draw[fill] (middle) circle (1pt); | |
325 | |
326 % nodes | |
327 \node[below] at (0.6, 0) {$u$}; | |
328 \node[below] at (2.2, 0) {$w$}; | |
329 \node[below] at (3.6, 0) {$y$}; | |
330 \end{tikzpicture} | |
331 \end{column} | |
332 \end{columns} | |
333 \end{center} | |
334 \end{frame} | |
335 } | |
336 | |
337 \defineUnit{cyk}{% | |
338 \begin{frame} | |
339 \frametitle{CYK} | |
340 \setbeamercovered{dynamic} | |
341 | |
342 \begin{definition}[Cocke-Younger-Kasami-Algorithmus] | |
16
a08f6e33cfb0
fourth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
343 Der \structure{CYK-Algorithmus} entscheidet das Wortproblem für kontextfreie Grammatiken in Chomsky-Normalform in $\Oh(n^3)$. \\ |
1 | 344 Gegeben eine \alert{Grammatik} $G = (V, \Sigma, P, S)$ in CNF und ein \alert{Wort} $w = a_1 \ldots a_n \in \Sigma^*$. |
345 Mit \[ V_{ij} := \left\{ A \in V \mid A \rightarrow_G^* \alert{a_i \ldots a_j} \right\}\] | |
346 ist \[ w \in L(G) \Leftrightarrow S \in V_{\alert{1n}} \] | |
347 \end{definition} | |
348 | |
349 \begin{align*} | |
350 V_{ii} &= \left\{ A \in V \mid (A \rightarrow a_i) \in P \right\} \\ | |
351 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\} | |
352 \end{align*} | |
353 \end{frame} | |
354 } | |
355 | |
356 \defineUnit{cykbeispiel}{% | |
357 \begin{frame} | |
358 \frametitle{CYK} | |
359 \setbeamercovered{dynamic} | |
360 | |
16
a08f6e33cfb0
fourth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
361 \begin{block}{CYK-Algorithmus} |
1 | 362 Kombiniere \alert{Teilwörter} zum ganzen Wort, wenn möglich. |
363 \begin{enumerate} | |
364 \item Initialisiere mit den \alert{$V_{ii}$}. | |
365 \item<3-5> Befülle die Tabelle von unten nach oben. | |
366 \end{enumerate} | |
367 \end{block} | |
368 | |
369 \[ 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
|
370 \vspace{2em} |
1 | 371 \begin{center} |
372 \extrarowsep=5pt | |
373 \begin{tabu}to .8\textwidth{r|X[c]|X[c]|X[c]|X[c]|} | |
374 \tabucline{2-2} | |
375 4 & \alt<-4>{}{$S,\ldots$} \\ \tabucline{2-3} | |
376 3 & \alt<-3>{}{$\emptyset$} & \alt<-3>{}{$S, A, C$} \\ \tabucline{2-4} | |
377 2 & \alt<-2>{}{$A$} & \alt<-2>{}{$B$} & \alt<-2>{}{$B$} \\ \tabucline{2-5} | |
378 1 & \alt<-1>{}{$B$} & \alt<1>{}{$A,C$} & \alt<1>{}{$A,C$} & \alt<1>{}{$A,C$} \\ \tabucline{2-5} | |
379 \multicolumn{1}{r}{} & \multicolumn{1}{c}{\alert{b}} & \multicolumn{1}{c}{\alert{a}} & \multicolumn{1}{c}{\alert{a}} & \multicolumn{1}{c}{\alert{a}} \\ | |
380 \end{tabu} | |
381 \end{center} | |
382 \end{frame} | |
383 } | |
384 | |
385 \defineUnit{pda}{% | |
386 \begin{frame} | |
387 \frametitle{Kellerautomaten} | |
388 \setbeamercovered{dynamic} | |
389 | |
390 \begin{definition}[Kellerautomat] | |
391 Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem | |
392 \begin{itemize} | |
393 \item endlichen Menge von \alert{Zuständen} $Q$ | |
394 \item endlichen \alert{Eingabealphabet} $\Sigma$ | |
395 \item endlichen \alert{Kelleralphabet} $\Gamma$ | |
396 \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$ | |
397 \item \alert{Startzustand} $q_0 \in Q$ | |
398 \item \alert{Kellerinitialisierung} $Z_0 \in \Gamma$ | |
399 \item Menge von \alert{Endzuständen} $F \subseteq Q$ | |
400 \end{itemize} | |
401 \end{definition} | |
402 | |
403 \begin{center} | |
404 \begin{tikzpicture}[automaton, node distance=4cm] | |
405 \node[state] (q0) {$q_i$}; | |
406 \node[state] (q1) [right of = q0] {$q_j$}; | |
407 | |
408 \draw[every edge] (q0) edge node {$a, X/\gamma$} (q1); | |
409 \end{tikzpicture} | |
410 \end{center} | |
411 \end{frame} | |
412 } | |
413 | |
414 \defineUnit{pdaakzeptanz}{% | |
415 \begin{frame} | |
416 \frametitle{Kellerautomaten} | |
417 \setbeamercovered{dynamic} | |
418 | |
419 \begin{definition}[Kellerautomat] | |
420 Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem | |
421 \begin{itemize} | |
422 \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$ | |
423 \end{itemize} | |
424 \end{definition} | |
425 | |
426 \vfill | |
427 | |
428 \begin{definition}[Akzeptanz] | |
429 Ein PDA $P$ akzeptiert $w \in \Sigma^*$ \alert{mit Endzustand} gdw | |
430 \[ \exists \alert{f \in F}, \gamma \in \Gamma^*.(q_0, w, Z_0) \rightarrow_P^* (\alert{f}, \epsilon, \gamma) \] | |
431 Ein PDA $P$ akzeptiert $w \in \Sigma^*$ \alert{mit leerem Keller} gdw | |
432 \[ \exists q \in Q.(q_0, w, Z_0) \rightarrow_P^* (q, \epsilon, \alert{\epsilon}) \] | |
433 \end{definition} | |
434 \end{frame} | |
435 } | |
436 | |
437 \defineUnit{pdabeispiel}{% | |
438 \begin{frame} | |
439 \frametitle{Kellerautomaten} | |
440 \setbeamercovered{dynamic} | |
441 | |
442 \begin{definition}[Kellerautomat] | |
443 Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem | |
444 \begin{itemize} | |
445 | |
446 \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$ | |
447 \end{itemize} | |
448 \end{definition} | |
449 | |
450 \vfill | |
451 | |
452 \begin{example}[] | |
453 PDA akzeptierend \alert{mit leerem Keller} zu $L = \left\{ a^nb^n \mid n \in \N \right\}$. | |
454 | |
455 \centering | |
456 \begin{tikzpicture}[automaton] | |
457 | |
458 \node[state, initial] (q0) {$q_0$}; | |
459 \node[state] (q1) [right of = q0] {$q_1$}; | |
460 | |
461 \draw[->] (q0) edge [bend left] node {$\epsilon, A/A$} (q1); | |
462 \draw[->] (q0) edge [bend right] node [below] {$\epsilon, Z_0/Z_0$} (q1); | |
463 | |
464 \draw[->] (q0) edge [loop above] node {$a, Z_0/AZ_0$} (q0); | |
465 \draw[->] (q0) edge [loop below] node {$a, A/AA$} (q0); | |
466 | |
467 \draw[->] (q1) edge [loop above] node {$b, A/\epsilon$} (q1); | |
468 \draw[->] (q1) edge [loop below] node {$\epsilon, Z_0/\epsilon$} (q1); | |
469 \end{tikzpicture} | |
470 \end{example} | |
471 \end{frame} | |
472 } | |
473 | |
474 \defineUnit{kontextfreiesprachen}{% | |
475 \begin{frame} | |
476 \frametitle{Kontextfreie Sprachen} | |
477 \setbeamercovered{dynamic} | |
478 | |
479 \begin{center} | |
480 \begin{tikzpicture}[node distance=3cm] | |
481 \node (CFG) {CFG}; | |
482 \node (CNF) [right of = CFG] {CNF}; | |
483 \node (PDAe) [right of = CNF] {PDA$_\epsilon$}; | |
484 \node (PDAf) [right of = PDAe] {PDA$_F$}; | |
485 | |
486 \draw [every edge, <->] (CFG) -- (CNF); | |
487 \draw [every edge, <->] (CNF) -- (PDAe); | |
488 \draw [every edge, <->] (PDAe) -- (PDAf); | |
489 \end{tikzpicture} | |
490 \end{center} | |
491 | |
492 \vfill | |
493 | |
494 \begin{itemize} | |
495 \item \alert{Abschlusseigenschaften} | |
496 \end{itemize} | |
497 \begin{table} | |
498 \begin{tabu}to \textwidth{X[c]|ccccc} | |
499 & Schnitt & Vereinigung & Komplement & Produkt & Stern \\ \tabucline{} | |
500 REG & ja & ja & ja & ja & ja\\ | |
501 CFL & nein & ja & nein & ja & ja | |
502 \end{tabu} | |
503 \end{table} | |
504 | |
505 \begin{itemize} | |
506 \item \alert{Entscheidbarkeit} | |
507 \end{itemize} | |
508 \begin{table} | |
509 \begin{tabu}to \textwidth{X[c]|cccc} | |
510 & Wortproblem & Leerheit & Äquivalenz & Schnittproblem\\ \tabucline{} | |
511 DFA & $\Oh(n)$ & ja & ja & ja \\ | |
512 CFG & $\Oh(n^3)$ & ja & nein & nein | |
513 \end{tabu} | |
514 \end{table} | |
515 \end{frame} | |
516 } |