Mercurial > 14ss.theoinf
comparison notes/tex/automata.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 | 60757c0ba1f0 |
| children | 0f7daeda8363 |
comparison
equal
deleted
inserted
replaced
| 15:60757c0ba1f0 | 16:a08f6e33cfb0 |
|---|---|
| 487 \end{frame} | 487 \end{frame} |
| 488 } | 488 } |
| 489 | 489 |
| 490 \defineUnit{rpl}{% | 490 \defineUnit{rpl}{% |
| 491 \begin{frame} | 491 \begin{frame} |
| 492 \frametitle{Pumping Lemma} | 492 \frametitle{Pumping Lemma für reguläre Sprachen} |
| 493 \setbeamercovered{dynamic} | 493 \setbeamercovered{dynamic} |
| 494 | 494 |
| 495 \begin{theorem}[Pumping Lemma für reguläre Sprachen] | 495 \begin{theorem}[Pumping Lemma für reguläre Sprachen] |
| 496 Sei $R \subseteq \Sigma^*$ regulär. Dann gibt es ein $n > 0$, so dass sich \alert{jedes} $z \in R$ mit $|z| \geq n$ so in $z = uvw$ zerlegen lässt, dass | 496 Sei $R \subseteq \Sigma^*$ regulär.\\ |
| 497 Dann gibt es ein $n > 0$, so dass sich \alert{jedes} $z \in R$ mit $|z| \geq n$ so in $z = uvw$ zerlegen lässt, dass | |
| 497 \begin{itemize} | 498 \begin{itemize} |
| 498 \item $v \neq \epsilon$ | 499 \item $v \neq \epsilon$ |
| 499 \item $|uv| \alert{\leq n}$ | 500 \item $|uv| \alert{\leq n}$ |
| 500 \item $\forall i \alert{\geq 0}. uv^iw \in R$ | 501 \item $\forall i \alert{\geq 0}. uv^iw \in R$ |
| 501 \end{itemize} | 502 \end{itemize} |
| 502 \end{theorem} | 503 \end{theorem} |
| 503 | 504 |
| 504 \vfill | 505 \vfill |
| 505 | 506 |
| 506 \begin{center} | 507 \begin{center} |
| 507 \begin{tikzpicture}[automaton] | 508 \begin{tikzpicture}[automaton, node distance=2.5cm] |
| 508 \node[state, initial] (q0) {}; | 509 \node[state, initial] (qi) {}; |
| 509 \node[state, fill=tumred!20] (q1) [right of=q0] {}; | 510 \node[state, fill=tumred!20] (q0) [right = 3 of qi] {}; |
| 510 \node[state, accepting] (q2) [right of=q1] {}; | 511 \node[state, fill=tumred!20] (q1) [above left of=q0] {}; |
| 511 | 512 \node[state, fill=tumred!20] (q2) [above right of=q0] {}; |
| 512 \draw[->, densely dashed] (q0) edge node {$u$} (q1); | 513 \node[state, accepting] (qf) [right = 3 of q0] {}; |
| 513 \draw[->, tumred] (q1) edge [loop above] node {$v$} (q1); | 514 |
| 514 \draw[->, densely dashed] (q1) edge node {$w$} (q2); | 515 \draw[->, densely dashed] (qi) edge node {$u$} (q0); |
| 516 \draw[tumred, densely dashed] | |
| 517 (q0) edge (q1) | |
| 518 (q1) edge (q2) | |
| 519 (q2) edge (q0); | |
| 520 \node[tumred] at (barycentric cs:q0=1,q1=1,q2=1) {$v$}; | |
| 521 \draw[->, densely dashed] (q0) edge node {$w$} (qf); | |
| 515 \end{tikzpicture} | 522 \end{tikzpicture} |
| 516 \end{center} | 523 \end{center} |
| 517 \end{frame} | 524 \end{frame} |
| 518 } | 525 } |
| 519 | 526 |