Mercurial > 13ss.theoinf

comparison notes/tex/grammars.tex @ 43:c14b92bfa07f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add missing slides; correct some errors
author Markus Kaiser <markus.kaiser@in.tum.de>
date Thu, 11 Jul 2013 21:57:50 +0200
parents 5d10471f5585
children 72ac27051d7e
comparison
equal deleted inserted replaced
42:35e8bb96da7b 43:c14b92bfa07f
60 L(G) := \left\{ w \in \Sigma^* \mid S \rightarrow_G^* w \right\} 60 L(G) := \left\{ w \in \Sigma^* \mid S \rightarrow_G^* w \right\}
61 \] 61 \]
62 Eine Sprache $L \subseteq \Sigma^*$ heißt \alert{kontextfrei} gdw es eine kontextfreie Grammatik $G$ gibt mit $L = L(G)$. 62 Eine Sprache $L \subseteq \Sigma^*$ heißt \alert{kontextfrei} gdw es eine kontextfreie Grammatik $G$ gibt mit $L = L(G)$.
63 \end{definition} 63 \end{definition}
64 \end{frame} 64 \end{frame}
65 }
66
67 \defineUnit{induktivesprachdefinition}{%
68 \begin{frame}
69 \frametitle{Induktive Sprachdefinition}
70 \setbeamercovered{dynamic}
71
72 \begin{block}{Induktive Sprachdefinition}
73 Die \alert{induktive Definition} ($\Longrightarrow$) erzeugt Wörter \alert{bottom-up}, setzt also kleine Wörter zu größeren zusammen.
74 \end{block}
75
76 \begin{example}[Vorbereitung 3]
77 Mit den Produktionen $S \rightarrow 0S1 \mid S11 \mid 1$:
78
79 \begin{align*}
80 1 &\in L_G(S) \\
81 u \in L_G(S) \quad \Longrightarrow \quad 0\alert{u}1 &\in L_G(S) \\
82 u \in L_G(S) \quad \Longrightarrow \quad \alert{u}11 &\in L_G(S)
83 \end{align*}
84
85 Also z.B:
86
87 \[
88 1 \in L_G(S) \Longrightarrow 0\alert{1}0 \in L_G(S) \Longrightarrow \alert{010}11 \in L_G(S)
89 \]
90 \end{example}
91 \end{frame}
65 } 92 }
66 93
67 \defineUnit{cnf}{% 94 \defineUnit{cnf}{%
68 \begin{frame} 95 \begin{frame}
69 \frametitle{CNF} 96 \frametitle{CNF}
168 Nützliche Symbole \alert{sind} erzeugend und erreichbar. Aber \alert{nicht} notwendigerweise umgekehrt. 195 Nützliche Symbole \alert{sind} erzeugend und erreichbar. Aber \alert{nicht} notwendigerweise umgekehrt.
169 \[ 196 \[
170 S \rightarrow AB \mid a, \quad A \rightarrow b 197 S \rightarrow AB \mid a, \quad A \rightarrow b
171 \] 198 \]
172 \end{theorem} 199 \end{theorem}
200 \end{frame}
201 }
202
203 \defineUnit{cfpl}{%
204 \begin{frame}
205 \frametitle{Pumping Lemma für CFLs}
206 \setbeamercovered{dynamic}
207
208 \begin{theorem}[Pumping Lemma für kontextfreie Sprachen]
209 Sei $L \subseteq \Sigma^*$ kontextfrei. 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
210 \begin{itemize}
211 \item $vx \alert{\neq \epsilon}$
212 \item $|vwx| \alert{\leq n}$
213 \item $\forall i \alert{\geq 0}. uv^iwx^iy \in L$
214 \end{itemize}
215 \end{theorem}
216
217 \vfill
218
219 \begin{center}
220 \begin{columns}
221 \begin{column}{.4\textwidth}
222 \begin{tikzpicture}
223 \coordinate (outer) at (2, 2.4);
224 \coordinate (middle) at (2.2, 1.2);
225 \coordinate (inner) at (2.2, 0.6);
226 % outer
227 \draw[fill=tumred!40] (0, 0) -- (1.2, 0) -- (middle) -- (3.2, 0) -- (4, 0) -- (outer) node[above] {$S$} -- (0, 0);
228 % middle
229 \draw[fill=tumgreen!40] (1.2, 0) -- (1.7, 0) -- (inner) -- (2.7, 0) -- (3.2, 0) -- (middle) -- (1.2, 0);
230 % inner
231 \draw[fill=tumblue!40] (1.7, 0) -- (inner) -- (2.7, 0) -- (1.7, 0);
232
233 % path
234 \draw[dashed, thick] (outer) -- (middle) -- (inner);
235 \draw[fill] (outer) circle (1pt);
236 \draw[fill] (middle) circle (1pt);
237 \draw[fill] (inner) circle (1pt);
238
239 % nodes
240 \node[below] at (0.6, 0) {$u$};
241 \node[below] at (1.45, 0) {$v$};
242 \node[below] at (2.2, 0) {$w$};
243 \node[below] at (2.95, 0) {$x$};
244 \node[below] at (3.6, 0) {$y$};
245 \end{tikzpicture}
246 \end{column}
247 \begin{column}{.4\textwidth}
248 \begin{tikzpicture}
249 \coordinate (outer) at (2, 2.4);
250 \coordinate (middle) at (2.2, 1.2);
251 \coordinate (inner) at (2.2, 0.6);
252 % outer
253 \draw[fill=tumred!40] (0, 0) -- (1.2, 0) -- (middle) -- (3.2, 0) -- (4, 0) -- (outer) node[above] {$S$} -- (0, 0);
254 % inner
255 \draw[fill=tumblue!40] (1.7, 0.6) -- (middle) -- (2.7, 0.6) -- (1.7, 0.6);
256
257 % path
258 \draw[dashed, thick] (outer) -- (middle);
259 \draw[fill] (outer) circle (1pt);
260 \draw[fill] (middle) circle (1pt);
261
262 % nodes
263 \node[below] at (0.6, 0) {$u$};
264 \node[below] at (2.2, 0) {$w$};
265 \node[below] at (3.6, 0) {$y$};
266 \end{tikzpicture}
267 \end{column}
268 \end{columns}
269 \end{center}
173 \end{frame} 270 \end{frame}
174 } 271 }
175 272
176 \defineUnit{cyk}{% 273 \defineUnit{cyk}{%
177 \begin{frame} 274 \begin{frame}
306 \draw[->] (q1) edge [loop below] node {$\epsilon, Z_0/\epsilon$} (q1); 403 \draw[->] (q1) edge [loop below] node {$\epsilon, Z_0/\epsilon$} (q1);
307 \end{tikzpicture} 404 \end{tikzpicture}
308 \end{example} 405 \end{example}
309 \end{frame} 406 \end{frame}
310 } 407 }
408
409 \defineUnit{kontextfreiesprachen}{%
410 \begin{frame}
411 \frametitle{Kontextfreie Sprachen}
412 \setbeamercovered{dynamic}
413
414 \begin{center}
415 \begin{tikzpicture}[node distance=3cm]
416 \node (CFG) {CFG};
417 \node (CNF) [right of = CFG] {CNF};
418 \node (PDAe) [right of = CNF] {PDA$_\epsilon$};
419 \node (PDAf) [right of = PDAe] {PDA$_F$};
420
421 \draw [every edge, <->] (CFG) -- (CNF);
422 \draw [every edge, <->] (CNF) -- (PDAe);
423 \draw [every edge, <->] (PDAe) -- (PDAf);
424 \end{tikzpicture}
425 \end{center}
426
427 \pause
428 \vfill
429
430 \begin{itemize}
431 \item \alert{Abschlusseigenschaften}
432 \end{itemize}
433 \begin{table}
434 \begin{tabu}to \textwidth{X[c]|ccccc}
435 & Schnitt & Vereinigung & Komplement & Produkt & Stern \\ \tabucline{}
436 REG & ja & ja & ja & ja & ja\\
437 CFL & nein & ja & nein & ja & ja
438 \end{tabu}
439 \end{table}
440
441 \begin{itemize}
442 \item \alert{Entscheidbarkeit}
443 \end{itemize}
444 \begin{table}
445 \begin{tabu}to \textwidth{X[c]|cccc}
446 & Wortproblem & Leerheit & Äquivalenz & Schnittproblem\\ \tabucline{}
447 DFA & $\Oh(n)$ & ja & ja & ja \\
448 CFG & $\Oh(n^3)$ & ja & nein & nein
449 \end{tabu}
450 \end{table}
451 \end{frame}
452 }