Mercurial > 13ss.theoinf
diff notes/tex/automatons.tex @ 41:5d10471f5585
move frame-definitions out of presentations
author | Markus Kaiser <markus.kaiser@in.tum.de> |
---|---|
date | Thu, 11 Jul 2013 20:42:36 +0200 |
parents | |
children | 35e8bb96da7b |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/notes/tex/automatons.tex Thu Jul 11 20:42:36 2013 +0200 @@ -0,0 +1,571 @@ +\defineUnit{dfa}{% +\begin{frame} + \frametitle{DFA} + + \begin{definition}[Deterministischer endlicher Automat] + Ein \alert{DFA} ist ein Tupel $M = (Q, \Sigma, \delta, q_0, F)$ aus einer/einem + \begin{itemize} + \item endlichen Menge von \alert{Zuständen} $Q$ + \item endlichen \alert{Eingabealphabet} $\Sigma$ + \item totalen \alert{Übergangsfunktion} $\delta : Q \times \Sigma \to Q$ + \item \alert{Startzustand} $q_0 \in Q$ + \item Menge von \alert{Endzuständen} $F \subseteq Q$ + \end{itemize} + \end{definition} + + \vfill + \pause + + \begin{center} + \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=] + \node[state, initial] (q0) {$q_0$}; + \node[state, accepting] (q1) [right of = q0] {$q_1$}; + \node[state] (q2) [right of = q1] {$q_2$}; + + \draw[->] (q0) edge [loop above] node {0} (q0); + \draw[->] (q2) edge [loop above] node {1} (q2); + \draw[->] (q0) edge [bend left] node {1} (q1); + \draw[->] (q1) edge [bend left] node {1} (q0); + \draw[->] (q1) edge [bend left] node {0} (q2); + \draw[->] (q2) edge [bend left] node {0} (q1); + \end{tikzpicture} + \end{center} +\end{frame} +} + +\defineUnit{nfa}{% +\begin{frame} + \frametitle{NFA} + \begin{definition}[Nicht-Deterministischer endlicher Automat] + Ein \alert{NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit + \begin{itemize} + \item $Q, \Sigma, q_0, F$ wie ein DFA + \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \to P(Q)$ + \end{itemize} + \end{definition} + + \vfill + \pause + + \begin{center} + \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=] + \node[state, initial] (q0) {$q_0$}; + \node[state, accepting] (q1) [right of = q0] {$q_1$}; +\draw[->] (q0) edge [loop above] node {0,1} (q0); \draw[->] (q0) edge node {1} (q1); \end{tikzpicture} \end{center} \end{frame} +} + +\defineUnit{enfa}{% +\begin{frame} + \frametitle{$\epsilon$-NFA} + \begin{definition}[NFA mit $\epsilon$-Übergängen] + Ein \alert{$\epsilon$-NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit + \begin{itemize} + \item $Q, \Sigma, q_0, F$ wie ein DFA + \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \to P(Q)$ + \end{itemize} + \end{definition} + + \vfill + \pause + + \begin{center} + \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=30, initial text=] + \node[state] (q1) {$q_1$}; + \node[state, initial] (q0) [left of = q1] {$q_0$}; + \node[state, accepting] (q2) [right of = q1] {$q_2$}; +\draw[->] (q0) edge [red] node {$\epsilon$} (q1); \draw[->] (q1) edge [loop above] node {0,1} (q1); \draw[->] (q1) edge node {1} (q2); \draw[->] (q0) edge [bend right, red] node {$\epsilon$} (q2); \end{tikzpicture} \end{center} \end{frame} +} + +\defineUnit{endlicheautomaten}{% +\begin{frame} + \frametitle{Endliche Automaten} + \begin{block}{Übergangsfunktionen} + Die Automaten $A = (Q, \Sigma, \delta, q_0, F)$ unterscheiden sich nur durch ihre Übergangsfunktionen. + + \begin{description} + \item[DFA] $\delta : Q \times \Sigma \to Q$ + \item[NFA] $\delta : Q \times \Sigma \to \alert{P(Q)}$ + \item[$\epsilon$-NFA] $\delta : Q \times \alert{\left( \Sigma \cup \{\epsilon\} \right)} \to \alert{P(Q)}$ + \end{description} + \end{block} + + \vfill + + \begin{theorem} + \alert{DFA}, \alert{NFA} und \alert{$\epsilon$-NFA} sind gleich mächtig und lassen sich ineinander umwandeln. + \end{theorem} +\end{frame} +} + +\defineUnit{regex}{% +\begin{frame} + \frametitle{Reguläre Ausdrücke} + \setbeamercovered{dynamic} + + \begin{definition}[Regulärer Ausdruck] + \alert{Reguläre Ausdrücke} sind induktiv definiert + \begin{itemize} + \item \alert{$\emptyset$} ist ein regulärer Ausdruck + \item \alert{$\epsilon$} ist ein regulärer Ausdruck + \item Für alle $a \in \Sigma$ ist \alert{$a$} ein regulärer Ausdruck + \item Sind $\alpha$ und $\beta$ reguläre Ausdrücke, dann auch + \begin{description} + \item[Konkatenation] \alert{$\alpha\beta$} + \item[Veroderung] \alert{$\alpha \mid \beta$} + \item[Wiederholung] \alert{$\alpha^*$} + \end{description} + \end{itemize} + Analoge Sprachdefinition, z.b. $L(\alpha\beta) = L(\alpha)L(\beta)$ + \end{definition} + + \begin{example} + $\alpha = (0|1)^*00$ \hfill $L(\alpha) = \left\{x \mid x \text{ Binärzahl}, x \mod 4 = 0 \right\}$ + \end{example} +\end{frame} +} + +\defineUnit{automatenkonversionen}{% +\begin{frame}[c] + \frametitle{Konversionen} + \setbeamercovered{dynamic} + + \begin{center} + \begin{tikzpicture}[node distance=2cm] + \node (nfa) {NFA}; + \node (dfa) [left of=nfa] {DFA}; + \node (enfa) [right of=nfa] {$\epsilon$-NFA}; + \node (re) [below of=nfa] {RE}; + + \draw [every edge, tumred] (nfa) -- (dfa); + \draw [every edge, tumred] (enfa) -- (nfa); + \draw [every edge] (dfa) -- (re); + \draw [every edge] (nfa) -- (re); + \draw [every edge, tumred] (re) -- (enfa); + \end{tikzpicture} + \end{center} +\end{frame} +} + +\defineUnit{rezunfa}{% +\begin{frame} + \frametitle{RE $\rightarrow$ $\epsilon$-NFA} + \setbeamercovered{dynamic} + + \begin{block}{Idee (Kleene)} + Für einen Ausdruck \alert{$\gamma$} wird rekursiv mit struktureller Induktion ein $\epsilon$-NFA konstruiert. + \end{block} + + \begin{tabu} to \linewidth {XXX} + \alert{$\gamma = \emptyset$} & \alert{$\gamma = \epsilon$} & \alert{$\gamma = a \in \Sigma$} \\ + \begin{tikzpicture}[automaton, small, baseline=(current bounding box.north)] + \node[state, initial] () {}; + \end{tikzpicture} & + + \begin{tikzpicture}[automaton, small, baseline=(current bounding box.north)] + \node[state, initial, accepting] () {}; + \end{tikzpicture} & + + \begin{tikzpicture}[automaton, small, baseline=(current bounding box.north)] + \node[state, initial] (i) {}; + \node[state, accepting] (j) [right of=i] {}; + + \draw[->] (i) edge node {$a$} (j); + \end{tikzpicture} \\ + \vspace{2em} + \alert{$\gamma = \alpha\beta$} \\ + \multicolumn3{c}{ + \begin{tikzpicture}[automaton, small] + \draw[tumgreen, fill=tumgreen!20] (-0.3, 1) rectangle (1.8, -1); + \node[tumgreen] () at (0.75, -1.2) {$N_\alpha$}; + + \draw[tumgreen, fill=tumgreen!20] (3.7, 1) rectangle (5.8, -1); + \node[tumgreen] () at (4.75, -1.2) {$N_\beta$}; + + \node[state, initial] (i) at (0, 0) {}; + \node[state] (j) at (1.5, 0.5) {}; + \node[state] (k) at (1.5, -0.5) {}; + \node[state] (l) at (4, 0) {}; + \node[state, accepting] (m) at (5.5, 0) {}; + + \draw[->] (j) edge node {$\epsilon$} (l); + \draw[->] (k) edge node {$\epsilon$} (l); + \end{tikzpicture} + }\\ + \end{tabu} +\end{frame} +} + +\defineUnit{rezuenfabeispiel}{% +\begin{frame} + \frametitle{RE $\rightarrow$ $\epsilon$-NFA} + \setbeamercovered{dynamic} + + \begin{tabu} to \linewidth {X} + \alert{$\gamma = \alpha \mid \beta$} \\ + \centering + \begin{tikzpicture}[automaton, small] + \draw[tumgreen, fill=tumgreen!20] (2, 1.5) rectangle (4.5, 0.5); + \node[tumgreen] () at (3.25, 0.3) {$N_\alpha$}; + + \draw[tumgreen, fill=tumgreen!20] (2, -0.5) rectangle (4.5, -1.5); + \node[tumgreen] () at (3.25, -1.7) {$N_\beta$}; + + \node[state, initial] (i) at (0, 0) {}; + + \node[state] (j) at (2.5, 1) {}; + \node[state, accepting] (k) at (4, 1) {}; + \node[state] (l) at (2.5, -1) {}; + \node[state, accepting] (m) at (4, -1) {}; + + \draw[->] (i) edge node {$\epsilon$} (j); + \draw[->] (i) edge node {$\epsilon$} (l); + \end{tikzpicture} \\ + \vfill + + \alert{$\gamma = \alpha^*$} \\ + \centering + \begin{tikzpicture}[automaton, small, bend angle=70] + \draw[tumgreen, fill=tumgreen!20] (2, 1) rectangle (4.5, -1); + \node[tumgreen] () at (3.25, -1.2) {$N_\alpha$}; + + \node[state, initial, accepting] (i) at (0, 0) {}; + + \node[state] (j) at (2.5, 0) {}; + \node[state, accepting] (k) at (4, 0.5) {}; + \node[state, accepting] (m) at (4, -0.5) {}; + + \draw[->] (i) edge node {$\epsilon$} (j); + \draw[->] (k) edge [bend right] node {$\epsilon$} (j); + \draw[->] (m) edge [bend left] node[above] {$\epsilon$} (j); + \end{tikzpicture} + \end{tabu} +\end{frame} +} + +\defineUnit{enfazunfa}{% +\begin{frame} + \frametitle{$\epsilon$-NFA $\rightarrow$ NFA} + \setbeamercovered{dynamic} + + \begin{block}{Idee} + Entferne $\epsilon$-Kanten durch das Bilden von $\epsilon$-Hüllen. + \begin{enumerate} + \item<1-> Entferne \alert{unnötige Knoten}. + \item<1,3-> Für jeden \alert{Pfad} der Form $\epsilon\ldots\epsilon \alert{a} \epsilon\ldots\epsilon$ verbinde Anfangs- und Endknoten mit einer \alert{$a$}-Kante. + \item<1,4-> Entferne alle \alert{$\epsilon$-Kanten} und unerreichbare Knoten. + \item<1,5-> Wurde das leere Wort akzeptiert mache den \alert{Anfangszustand} zum Endzustand. + \end{enumerate} + \end{block} + + \vfill + + \begin{tikzpicture}[automaton, bend angle=40, node distance=2.1cm] + \useasboundingbox (-1.4,2) rectangle (9, -2); + + \node<-4>[state, initial] (q0) {$q_0$}; + \node[state] (q2) [right = 3.2cm of q0] {$q_2$}; + \node[state] (q3) [right of = q2] {$q_3$}; + \node[state, accepting] (q4) [right of = q3] {$q_4$}; + + \draw[->] (q2) edge node {$0$} (q3); + \draw[->] (q3) edge node {$1$} (q4); + + \draw<1-4>[->] (q3) edge [bend right] node [above] {$\epsilon$} (q2); + \draw[->] (q4) edge [bend right] node [above] {$1$} (q3); + \draw<1-4>[->] (q0) edge [bend right=20] node [below] {$\epsilon$} (q4); + + \node<1>[state] (q1) [right of = q0] {$q_1$}; + \draw<1>[->] (q0) edge node {$\epsilon$} (q1); + \draw<1>[->] (q1) edge node {$1$} (q2); + + \node<2>[state, fill=tumred!20] (q1) [right of = q0] {$q_1$}; + \draw<2>[->, tumred] (q0) edge node {$\epsilon$} (q1); + \draw<2>[->, tumred] (q1) edge node {$0$} (q2); + \draw<2->[->, tumblue] (q0) edge [bend left] node {$0$} (q2); + + \draw<3,4,5>[->, tumred] (q0) edge [bend right=20] node [below] {$\epsilon$} (q4); + \draw<3>[->, tumred] (q4) edge [bend right] node [above] {$1$} (q3); + \draw<3,4>[->, tumred] (q3) edge [bend right] node [above] {$\epsilon$} (q2); + \draw<3->[->, tumgreen] (q0) edge node {$1$} (q2); + + \draw<4->[->, tumgreen] (q2) edge [loop above] node [above] {$0$} (q2); + \draw<4->[->, tumgreen] (q3) edge [loop above] node [above] {$0$} (q3); + \draw<4->[->, tumgreen] (q0) edge [bend right=20] node [above] {$1$} (q3); + \draw<4->[->, tumgreen] (q4) edge [bend right=70] node [above] {$1$} (q2); + + \node<5>[state, initial, accepting, fill=tumgreen!20] (q0) {$q_0$}; + + \node<6->[state, initial, accepting] (q0) {$q_0$}; + \end{tikzpicture} +\end{frame} +} + +\defineUnit{nfazudfa}{% +\begin{frame} + \frametitle{NFA $\rightarrow$ DFA} + \setbeamercovered{dynamic} + + \begin{block}{Idee (Potenzmengenkonstruktion)} + Konstruiere aus einem NFA $N = (Q, \Sigma, \delta, q_0, F)$ einen DFA $D = (P(Q), \Sigma, \overline{\delta}, \{q_0\}, F_M)$ mit Zuständen aus \alert{$P(Q)$}. + + \begin{itemize} + \item $\overline{\delta}: \alert{P(Q)} \times \Sigma \to P(Q)$ \\ + \[\overline{\delta}(S, a) := \bigcup_{q \in S} \delta(q, a)\] + \item $F_M := \left\{S \subseteq Q \mid \alert{S \cap F} \neq \emptyset\right\}$ + \end{itemize} + \end{block} + + \begin{tikzpicture}[automaton, bend angle=20, node distance=2.1cm] + \useasboundingbox (-1.4,2) rectangle (9, -2); + + \node[state, initial] (q0) {$q_0$}; + \node[state, accepting] (q1) [right of = q0] {$q_1$}; + + \draw[->] (q0) edge [loop above] node {$0,1$} (q0); + \draw[->] (q0) edge node {$1$} (q1); + + \node<2->(sep) [right of = q1] {$\rightarrow$}; + + \node<2->[state, initial, inner sep=1pt] (pq0) [right of = sep] {$q_{\{0\}}$}; + + \node<3->[state, accepting, inner sep=0pt] (pq01) [right of = pq0] {$q_{\{0,1\}}$}; + \draw<3->[->] (pq0) edge [loop above] node {$0$} (pq0); + \draw<3->[->] (pq0) edge [bend left] node {$1$} (pq01); + + \draw<4->[->] (pq01) edge [loop above] node {$1$} (pq01); + \draw<4->[->] (pq01) edge [bend left] node {$0$} (pq0); + + \end{tikzpicture} +\end{frame} +} + +\defineUnit{produktautomat}{% +\begin{frame} + \frametitle{produktautomat} + \setbeamercovered{dynamic} + \begin{theorem} + sind $m_1 = (q_1, \sigma, \delta_1, s_1, f_1)$ und $m_2 = (q_2, \sigma, \delta_2, s_2, f_2)$ dfas, dann ist der \alert{produkt-automat} + + \begin{align*} + m &:= (\alert{q_1 \times q_2}, \sigma, \delta, (s_1, s_2), f_1 \times f_2) \\ + \delta\left( (q_1, q_2), a \right) &:= \left( \alert{\delta_1}(q_1, a), \alert{\delta_2}(q_2, a) \right) + \end{align*} + + ein dfa, der $l(m_1) \cap l(m_2)$ akzeptiert. + \end{theorem} +\end{frame} +} + +\defineUnit{regexrechnen}{% +\begin{frame} + \frametitle{Nochmal Reguläre Ausdrücke} + \setbeamercovered{dynamic} + + \begin{theorem} + Die regulären Ausdrücke $\mathfrak{R}$ über einem Alphabet $\Sigma$ bilden mit Konkatenation $\circ$ und Veroderung $\mid$ einen \alert{Halbring} $\langle \mathfrak{R}, \mid, \circ, \emptyset, \epsilon \rangle$. + + \begin{itemize} + \item \alert{Assoziative} Operationen + \item Veroderung \alert{kommutativ} + \item \alert{Distributivität}: $\alpha (\beta \mid \gamma) \equiv \alpha\beta \mid \alpha\gamma$ + \item $\emptyset$ \alert{neutral} bezüglich Oder + \item $\epsilon$ \alert{neutral} bezüglich Konkatenation + \end{itemize} + \end{theorem} + + \begin{example} + \[ + 1\psi \mid 0\phi \mid \psi \equiv 0 \phi \mid (1 \mid \epsilon) \psi + \] + \end{example} +\end{frame} +} + +\defineUnit{arden}{% +\begin{frame} + \frametitle{Ardens Lemma} + \setbeamercovered{dynamic} + + \begin{theorem}[Ardens Lemma] + Sind $A$, $B$ und $X$ Sprachen mit $\epsilon \not \in A$, dann gilt + \[ + X = AX \cup B \Longrightarrow X = A^* B + \] + Speziell gilt für reguläre Ausdrücke + \[ + X \equiv \alpha X \mid \beta \Longrightarrow X \equiv \alpha^* \beta + \] + \end{theorem} + + \begin{example} + \[ + \psi \equiv 0 \psi \mid (1 \mid \epsilon) \phi \Longrightarrow \psi \equiv 0^*(1\mid \epsilon) \phi + \] + \end{example} +\end{frame} +} + +\defineUnit{nfazure}{% +\begin{frame} + \frametitle{NFA $\rightarrow$ RE} + \setbeamercovered{dynamic} + + \begin{block}{Idee} + Erzeuge ein Gleichungssystem aus allen Zuständen. + \begin{enumerate} + \item<1,2-> Ausdruck für jeden Zustand + \item<1,3-> Auflösen nach $X_0$ mit Algebra und Ardens Lemma + \end{enumerate} + \end{block} + \begin{columns}<2-> + \begin{column}[b]{.65\textwidth} + \begin{align*} + X_0 &\equiv 1X_0 \mid 0X_1 \\ + &\equiv \uncover<4->{1X_0 \mid 00^*(\epsilon \mid 1X_0)} \\ + &\equiv \uncover<4->{(1 \mid 00^*1) X_0 \mid 00^*} \\ + &\equiv \uncover<4->{(1 \mid 00^*1)^*(00^*)} \\ + \\ + X_1 &\equiv 1X_0 \mid 0X_1 \alt<3->{\mid \epsilon}{\alert{\mid \epsilon}} \\ + &\equiv \uncover<3-> {0X_1 \mid (\epsilon \mid 1 X_0)}\\ + &\equiv \uncover<3-> {\alt<-2,4->{0^*(\epsilon \mid 1X_0)}{\alert{0^*(\epsilon \mid 1X_0)}}} + \end{align*} + \end{column} + \begin{column}[t]{.35\textwidth} + \begin{tikzpicture}[automaton] + \node[state, initial] (q0) {$q_0$}; + \node[state, accepting] (q1) [below of=q0] {$q_1$}; + + \draw[->] (q0) edge [bend right] node [left] {$0$} (q1); + \draw[->] (q1) edge [bend right] node [right] {$1$} (q0); + \draw[->] (q0) edge [loop right] node {$1$} (q0); + \draw[->] (q1) edge [loop right] node {$0$} (q1); + \end{tikzpicture} + \end{column} + \end{columns} +\end{frame} +} + +\defineUnit{rpl}{% +\begin{frame} + \frametitle{Pumping Lemma} + \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 + \begin{itemize} + \item $v \neq \epsilon$ + \item $|uv| \alert{\leq n}$ + \item $\forall i \alert{\geq 0}. uv^iw \in R$ + \end{itemize} + \end{theorem} + + \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] {}; + + \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); + \end{tikzpicture} + \end{center} +\end{frame} +} + +\defineUnit{rplanwenden}{% +\begin{frame} + \frametitle{Nichtregularität beweisen} + \setbeamercovered{dynamic} + + \begin{block}{Idee} + Gegenbeispiel fürs Pumpinglemma suchen. + \[ + \alert{\forall} n \in \N_0 \alert{\exists} z \in L. |z| \geq n \ \alert{\forall} u,v,w. \ z = uvw \ \text{\alert{nicht} pumpbar} + \] + \end{block} + + \vfill + + \begin{example}<2-> + Ist $L = \left\{ a^ib^i \mid i \in \N_0 \right\}$ regulär? + \begin{enumerate} + \item \alert{Sei $n$} PL-Zahl + \item \alert{Wähle} $\alert{z} = a^nb^n$ + \item Dann ist \alert{$z = uvw$} mit \alert{$|uv| \leq n$}, hier: $v=a^k$ mit $k > 0$ + \item Dann ist $uv^0w \not \in L$ + \item Damit ist L \alert{nicht} regulär. + \end{enumerate} + \end{example} +\end{frame} +} + +\defineUnit{aequivalenteZustaende}{% +\begin{frame} + \frametitle{Äquivalenzen} + \setbeamercovered{dynamic} + + \begin{definition}[Äquivalente Worte] + Jede Sprache $L \subseteq \Sigma^*$ induziert eine Äquivalenzrelation $\alert{\equiv_L \subseteq \Sigma^* \times \Sigma^*}$: + \[ + u \alert{\equiv_L} v \Longleftrightarrow \left( \forall w \in \Sigma^*. \alert{uw} \in L \Leftrightarrow \alert{vw} \in L\right) + \] + \end{definition} + + \vfill + + \pause + + \begin{definition}[Äquivalente Zustände] + Zwei Zustände im DFA $A$ sind \alert{äquivalent} wenn sie die selbe Sprache akzeptieren. + + \[ + p \alert{\equiv_A} q \Longleftrightarrow \left( \forall w \in \Sigma^*. \alert{\hat{\delta}(p, w)} \in F \Leftrightarrow \alert{\hat{\delta}(q, w)} \in F \right) + \] + \end{definition} +\end{frame} +} + +\defineUnit{unterscheidbareZustaende}{% +\begin{frame} + \frametitle{Unterscheidbare Zustände} + \setbeamercovered{dynamic} + + \begin{definition}[Unterscheidbarkeit] + Zwei Zustände sind \alert{unterscheidbar}, wenn sie unterschiedliche Sprachen akzeptieren. + \[ + p \alert{\not\equiv_A} q \Longleftrightarrow \left( \exists w \in \Sigma^*. \hat{\delta}(p, w) \alert{\in} F \wedge \hat{\delta}(q, w) \alert{\not\in} F \right) + \] + \end{definition} + + \begin{theorem} + Sind $\delta(p, a)$ und $\delta(q, a)$ unterscheidbar, dann auch $p$ und $q$. + \end{theorem} + + \pause + + \begin{tikzpicture}[automaton, bend angle=40, node distance=2.5cm] + \node[state, initial] (q0) {$q_0$}; + \node[state] (q1) [right of = q0] {$q_1$}; + \node[state] (q2) [right of = q1] {$q_2$}; + \node[state, accepting] (q3) [right of = q2] {$q_3$}; + + \draw[->] (q0) edge node {$a$} (q1); + \draw[->] (q0) edge [bend left] node {$b$} (q2); + \draw[->] (q1) edge node {$a$} (q2); + \draw[->] (q1) edge [bend right] node {$b$} (q3); + \draw[->] (q2) edge node {$a,b$} (q3); + \draw[->] (q3) edge [loop right] node {$a,b$} (q3); + + \node<3>[state, fill=tumred!35] () at (q2) {$q_2$}; + \node<3->[state, accepting, fill=tumgreen!35] () at (q3) {$q_3$}; + + \node<4>[state, fill=tumred!35] () at (q0) {$q_0$}; + \node<4>[state, fill=tumred!35] () at (q1) {$q_1$}; + \draw<4>[->, tumred] (q0) edge [bend left] node {$b$} (q2); + \draw<4>[->, tumgreen] (q1) edge [bend right] node {$b$} (q3); + \end{tikzpicture} +\end{frame} +}