Mercurial > 14ss.theoinf
diff 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 |
line wrap: on
line diff
--- a/notes/tex/automata.tex Fri May 09 11:28:33 2014 +0200 +++ b/notes/tex/automata.tex Sat May 10 19:39:01 2014 +0200 @@ -489,11 +489,12 @@ \defineUnit{rpl}{% \begin{frame} - \frametitle{Pumping Lemma} + \frametitle{Pumping Lemma für reguläre Sprachen} \setbeamercovered{dynamic} \begin{theorem}[Pumping Lemma für reguläre Sprachen] - 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 + 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 \begin{itemize} \item $v \neq \epsilon$ \item $|uv| \alert{\leq n}$ @@ -504,14 +505,20 @@ \vfill \begin{center} - \begin{tikzpicture}[automaton] - \node[state, initial] (q0) {}; - \node[state, fill=tumred!20] (q1) [right of=q0] {}; - \node[state, accepting] (q2) [right of=q1] {}; + \begin{tikzpicture}[automaton, node distance=2.5cm] + \node[state, initial] (qi) {}; + \node[state, fill=tumred!20] (q0) [right = 3 of qi] {}; + \node[state, fill=tumred!20] (q1) [above left of=q0] {}; + \node[state, fill=tumred!20] (q2) [above right of=q0] {}; + \node[state, accepting] (qf) [right = 3 of q0] {}; - \draw[->, densely dashed] (q0) edge node {$u$} (q1); - \draw[->, tumred] (q1) edge [loop above] node {$v$} (q1); - \draw[->, densely dashed] (q1) edge node {$w$} (q2); + \draw[->, densely dashed] (qi) edge node {$u$} (q0); + \draw[tumred, densely dashed] + (q0) edge (q1) + (q1) edge (q2) + (q2) edge (q0); + \node[tumred] at (barycentric cs:q0=1,q1=1,q2=1) {$v$}; + \draw[->, densely dashed] (q0) edge node {$w$} (qf); \end{tikzpicture} \end{center} \end{frame}