# HG changeset patch
# User Markus Kaiser <markus.kaiser@in.tum.de>
# Date 1399627713 -7200
# Node ID 60757c0ba1f0e4891573d0e2da024558ac66d837
# Parent  d5b561a49683652baa4376f9df8a132cd7853af1
rename automata file; add complete notes

diff -r d5b561a49683 -r 60757c0ba1f0 notes/tex/automata.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/automata.tex	Fri May 09 11:28:33 2014 +0200
@@ -0,0 +1,691 @@
+\defineUnit{alphabet}{%
+\begin{frame}
+    \frametitle{Alphabete}
+
+    \begin{definition}
+        \begin{itemize}
+            \item Ein \structure{Alphabet} $\Sigma$ ist eine endliche Menge.
+            \item Ein \structure{Wort} über $\Sigma$ ist eine endliche Folge von Zeichen.
+            \item Eine Teilmenge $L \subseteq \Sigma^*$ ist eine \structure{formale Sprache}
+        \end{itemize}
+    \end{definition}
+
+    \vfill
+
+    \begin{definition}[Operationen auf Sprachen]
+        \begin{itemize}
+            \item $\structure{AB} \defeq \left\{ uv \mid u \in A \wedge v \in B \right\}$
+            \item $\structure{A^{n+1}} \defeq A^nA $,\qquad\qquad $\structure{A^0} \defeq \{\epsilon\}$
+            \item $\structure{A^*} \defeq \bigcup_{n \in \N_0} A^n$
+        \end{itemize}
+    \end{definition}
+\end{frame}
+}
+
+\defineUnit{dfa}{%
+\begin{frame}
+    \frametitle{DFA}
+
+    \begin{definition}[Deterministischer endlicher Automat]
+        Ein \structure{DFA} ist ein Tupel $M = (Q, \Sigma, \delta, q_0, F)$ aus einer/einem
+        \begin{itemize}
+            \item endlichen Menge von \structure{Zuständen} $Q$
+            \item endlichen \structure{Eingabealphabet} $\Sigma$
+            \item totalen \structure{Übergangsfunktion} $\delta : Q \times \Sigma \to Q$
+            \item \structure{Startzustand} $q_0 \in Q$
+            \item Menge von \structure{Endzuständen} $F \subseteq Q$
+        \end{itemize}
+    \end{definition}
+
+    \vfill
+
+    \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 \structure{NFA} ist ein Tupel $N = (Q, \Sigma, \delta, S, F)$ mit
+        \begin{itemize}
+            \item $Q, \Sigma, F$ wie ein DFA
+            \item Menge von \structure{Startzuständen} $S \subseteq F$
+            \item \structure{Übergangsfunktion} $\delta : Q \times \Sigma \to \powerset{Q}$
+        \end{itemize}
+    \end{definition}
+
+    \vfill
+
+    \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 \structure{$\epsilon$-NFA} ist ein Tupel $N = (Q, \Sigma, \delta, S, F)$ mit
+        \begin{itemize}
+            \item $Q, \Sigma, F$ wie ein DFA
+            \item Menge von \structure{Startzuständen} $S \subseteq F$
+            \item \structure{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \to \powerset{Q}$
+        \end{itemize}
+    \end{definition}
+
+    \vfill
+
+    \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{\powerset{Q}}$
+            \item[$\epsilon$-NFA] $\delta : Q \times \alert{\left( \Sigma \cup \{\epsilon\} \right)} \to \alert{\powerset{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]
+        \structure{Reguläre Ausdrücke} sind induktiv definiert
+        \begin{itemize}
+            \item \structure{$\emptyset$} ist ein regulärer Ausdruck
+            \item \structure{$\epsilon$} ist ein regulärer Ausdruck
+            \item Für alle $a \in \Sigma$ ist \structure{$a$} ein regulärer Ausdruck
+            \item Sind $\alpha$ und $\beta$ reguläre Ausdrücke, dann auch
+                \begin{description}[Konkatenation]
+                    \item[Konkatenation] \structure{$\alpha\beta$}
+                    \item[Veroderung] \structure{$\alpha \mid \beta$}
+                    \item[Wiederholung] \structure{$\alpha^*$}
+                \end{description}
+        \end{itemize}
+        Analoge Sprachdefinition, z.b. $L(\alpha\beta) = L(\alpha)L(\beta)$
+    \end{definition}
+
+    \begin{example}
+        \begin{itemize}
+            \item $\alpha = (0|1)^*00$
+            \item Worte bestehen aus einer beliebigen Folge von Einsen und Nullen gefolgt von zwei Nullen.
+            \item $L(\alpha) \supseteq \left\{x \mid x \text{ Binärzahl}, x \mod 4 = 0 \right\}$
+        \end{itemize}
+    \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{rezuenfa}{%
+\begin{frame}
+    \frametitle{RE $\rightarrow$ $\epsilon$-NFA}
+    \setbeamercovered{dynamic}
+
+    \begin{block}{Thompson-Konstruktion}
+        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}
+
+\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] (k) at (4, 1) {};
+            \node[state] (l) at (2.5, -1) {};
+            \node[state] (m) at (4, -1) {};
+
+            \node[state, accepting] (n) at (6.5, 0) {};
+
+            \draw[->] (i) edge node {$\epsilon$} (j);
+            \draw[->] (i) edge node {$\epsilon$} (l);
+            \draw[->] (k) edge node {$\epsilon$} (n);
+            \draw[->] (m) edge node {$\epsilon$} (n);
+        \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] (i) at (0, 0) {};
+
+            \node[state] (j) at (2.5, 0) {};
+            \node[state] (k) at (4, 0.5) {};
+            \node[state] (m) at (4, -0.5) {};
+
+            \node[state, accepting] (n) at (6.5, 0) {};
+
+            \draw[->] (i) edge node {$\epsilon$} (j);
+            \draw[->] (i) edge[bend right=90] node {$\epsilon$} (n);
+
+            \draw[->] (k) edge [bend right] node {$\epsilon$} (j);
+            \draw[->] (m) edge [bend left] node[above] {$\epsilon$} (j);
+            \draw[->] (k) edge node {$\epsilon$} (n);
+            \draw[->] (m) edge node {$\epsilon$} (n);
+        \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}{Potenzmengenkonstruktion}
+        Konstruiere einen Automaten, der \structure{alle möglichen Pfade} gleichzeitig berücksichtigt.
+        Gegeben ein NFA $(Q, \Sigma, \delta, S, F)$, konstruiere einen DFA mit Zuständen aus \alert{$\powerset{Q}$}.
+
+        \begin{itemize}
+            \item Starte in $\left\{ S \right\}$
+            \item Die Übergangsfunktion speichert \structure{alle möglichen Schritte}
+                \begin{align}
+                    \overline{\delta}: \powerset{Q} \times \Sigma &\to \powerset{Q} \\
+                    (M, a) &\mapsto \bigcup_{q \in M} \delta(q, a)
+                \end{align}
+            \item $M$ ist Endzustand wenn $F \cap M \neq \emptyset$
+        \end{itemize}
+    \end{block}
+
+    \begin{tikzpicture}[automaton, bend angle=20, node distance=2.1cm]
+        \tikzstyle{every state}=[minimum width=1cm, pretty]
+        \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 \structure{Äquivalenzrelation $\equiv_L \subseteq \Sigma^* \times \Sigma^*$}
+        \[ u \structure{\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 \structure{äquivalent} wenn sie die selbe Sprache akzeptieren.
+        \[ p \structure{\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 \structure{unterscheidbar}, wenn sie unterschiedliche Sprachen akzeptieren.
+        \[ p \structure{\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}
+}
+
+\defineUnit{quotientenautomat}{%
+\begin{frame}[t]
+    \frametitle{DFA minimieren}
+    \setbeamercovered{dynamic}
+
+    \begin{block}{Quotientenautomat}
+        \begin{enumerate}
+            \item Entferne alle von $q_0$ \alert{nicht erreichbaren} Zustände
+            \item<1, 3-> Berechne die \alert{unterscheidbaren} Zustände
+            \item<1, 6-> \alert{Kollabiere} die äquivalenten Zustände
+        \end{enumerate}
+    \end{block}
+
+    \vfill
+
+    \begin{columns}[c]<2->
+        \begin{column}{.5\textwidth}<3->
+            \begin{center}
+                \begin{tabu}to .8\textwidth{|X[c]|X[c]|X[c]|X}
+                    \multicolumn{2}{l}{0} \\ \tabucline{1-1}
+                    \alt<-4>{}{\textcolor{tumgreen}{$1/a$}} & \multicolumn{2}{l}{1} \\ \tabucline{1-2}
+                    \alt<-4>{}{\textcolor{tumgreen}{$1/a$}} &  & \multicolumn{2}{l}{2} \\ \tabucline{1-3}
+                    \alt<-3>{}{\textcolor{tumred}{$\times$}} &  \alt<-3>{}{\textcolor{tumred}{$\times$}}& \alt<-3>{} {\textcolor{tumred}{$\times$}}& 3 \\ \tabucline{1-3}
+                \end{tabu}
+            \end{center}
+        \end{column}
+        \begin{column}{.5\textwidth}
+            \begin{tikzpicture}[automaton, node distance=2.5cm]
+                \useasboundingbox (-0.5, -0.5) rectangle (2, -2);
+
+                \node[state, initial] (q0) {$q_0$};
+                \node<-5>[state] (q1) [right of = q0] {$q_1$};
+                \node<-5>[state] (q2) [below of = q0] {$q_2$};
+                \node<6>[state, fill=tumred!40] (q12) [right of = q0] {$q_{12}$};
+                \node[state, accepting] (q3) [right of = q2] {$q_3$};
+
+                \draw<-5>[->] (q0) edge node {$a$} (q1);
+                \draw<-5>[->] (q0) edge node {$b$} (q2);
+                \draw<-5>[->] (q1) edge node {$a,b$} (q3);
+                \draw<-5>[->] (q2) edge node {$a,b$} (q3);
+                \draw[->] (q3) edge [loop right] node [above] {$a,b$} (q3);
+
+                \draw<6>[->] (q12) edge node {$a,b$} (q3);
+                \draw<6>[->] (q0) edge node {$a,b$} (q12);
+            \end{tikzpicture}
+        \end{column}
+    \end{columns}
+\end{frame}
+}
+
+\defineUnit{regulaeresprachen}{%
+\begin{frame}
+    \frametitle{Reguläre Sprachen}
+    \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] (nfa) -- (dfa);
+            \draw [every edge] (enfa) -- (nfa);
+            \draw [every edge] (dfa) -- (re);
+            \draw [every edge] (nfa) -- (re);
+            \draw [every edge] (re) -- (enfa);
+        \end{tikzpicture}
+    \end{center}
+
+    \vfill
+
+    \begin{theorem}
+        Für eine Darstellung $D$ einer regulären Sprache ist \alert{entscheidbar}:
+        \vspace{1em}
+        \begin{description}
+            \item[Wortproblem] Gegeben $w$, gilt $w \in L(D)$?
+            \item[Leerheitsproblem] Ist $L(D) = \emptyset$?
+            \item[Endlichkeitsproblem] Ist $|L(D)| < \infty$?
+            \item[Äquivalenzproblem] Gilt $L(D_1) = L(D_2)$?
+        \end{description}
+    \end{theorem}
+\end{frame}
+}
diff -r d5b561a49683 -r 60757c0ba1f0 notes/tex/automatons.tex
--- a/notes/tex/automatons.tex	Mon May 05 14:41:06 2014 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,691 +0,0 @@
-\defineUnit{alphabet}{%
-\begin{frame}
-    \frametitle{Alphabete}
-
-    \begin{definition}
-        \begin{itemize}
-            \item Ein \structure{Alphabet} $\Sigma$ ist eine endliche Menge.
-            \item Ein \structure{Wort} über $\Sigma$ ist eine endliche Folge von Zeichen.
-            \item Eine Teilmenge $L \subseteq \Sigma^*$ ist eine \structure{formale Sprache}
-        \end{itemize}
-    \end{definition}
-
-    \vfill
-
-    \begin{definition}[Operationen auf Sprachen]
-        \begin{itemize}
-            \item $\structure{AB} \defeq \left\{ uv \mid u \in A \wedge v \in B \right\}$
-            \item $\structure{A^{n+1}} \defeq A^nA $,\qquad\qquad $\structure{A^0} \defeq \{\epsilon\}$
-            \item $\structure{A^*} \defeq \bigcup_{n \in \N_0} A^n$
-        \end{itemize}
-    \end{definition}
-\end{frame}
-}
-
-\defineUnit{dfa}{%
-\begin{frame}
-    \frametitle{DFA}
-
-    \begin{definition}[Deterministischer endlicher Automat]
-        Ein \structure{DFA} ist ein Tupel $M = (Q, \Sigma, \delta, q_0, F)$ aus einer/einem
-        \begin{itemize}
-            \item endlichen Menge von \structure{Zuständen} $Q$
-            \item endlichen \structure{Eingabealphabet} $\Sigma$
-            \item totalen \structure{Übergangsfunktion} $\delta : Q \times \Sigma \to Q$
-            \item \structure{Startzustand} $q_0 \in Q$
-            \item Menge von \structure{Endzuständen} $F \subseteq Q$
-        \end{itemize}
-    \end{definition}
-
-    \vfill
-
-    \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 \structure{NFA} ist ein Tupel $N = (Q, \Sigma, \delta, S, F)$ mit
-        \begin{itemize}
-            \item $Q, \Sigma, F$ wie ein DFA
-            \item Menge von \structure{Startzuständen} $S \subseteq F$
-            \item \structure{Übergangsfunktion} $\delta : Q \times \Sigma \to \powerset{Q}$
-        \end{itemize}
-    \end{definition}
-
-    \vfill
-
-    \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 \structure{$\epsilon$-NFA} ist ein Tupel $N = (Q, \Sigma, \delta, S, F)$ mit
-        \begin{itemize}
-            \item $Q, \Sigma, F$ wie ein DFA
-            \item Menge von \structure{Startzuständen} $S \subseteq F$
-            \item \structure{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \to \powerset{Q}$
-        \end{itemize}
-    \end{definition}
-
-    \vfill
-
-    \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{\powerset{Q}}$
-            \item[$\epsilon$-NFA] $\delta : Q \times \alert{\left( \Sigma \cup \{\epsilon\} \right)} \to \alert{\powerset{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]
-        \structure{Reguläre Ausdrücke} sind induktiv definiert
-        \begin{itemize}
-            \item \structure{$\emptyset$} ist ein regulärer Ausdruck
-            \item \structure{$\epsilon$} ist ein regulärer Ausdruck
-            \item Für alle $a \in \Sigma$ ist \structure{$a$} ein regulärer Ausdruck
-            \item Sind $\alpha$ und $\beta$ reguläre Ausdrücke, dann auch
-                \begin{description}[Konkatenation]
-                    \item[Konkatenation] \structure{$\alpha\beta$}
-                    \item[Veroderung] \structure{$\alpha \mid \beta$}
-                    \item[Wiederholung] \structure{$\alpha^*$}
-                \end{description}
-        \end{itemize}
-        Analoge Sprachdefinition, z.b. $L(\alpha\beta) = L(\alpha)L(\beta)$
-    \end{definition}
-
-    \begin{example}
-        \begin{itemize}
-            \item $\alpha = (0|1)^*00$
-            \item Worte bestehen aus einer beliebigen Folge von Einsen und Nullen gefolgt von zwei Nullen.
-            \item $L(\alpha) \supseteq \left\{x \mid x \text{ Binärzahl}, x \mod 4 = 0 \right\}$
-        \end{itemize}
-    \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{rezuenfa}{%
-\begin{frame}
-    \frametitle{RE $\rightarrow$ $\epsilon$-NFA}
-    \setbeamercovered{dynamic}
-
-    \begin{block}{Thompson-Konstruktion}
-        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}
-
-\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] (k) at (4, 1) {};
-            \node[state] (l) at (2.5, -1) {};
-            \node[state] (m) at (4, -1) {};
-
-            \node[state, accepting] (n) at (6.5, 0) {};
-
-            \draw[->] (i) edge node {$\epsilon$} (j);
-            \draw[->] (i) edge node {$\epsilon$} (l);
-            \draw[->] (k) edge node {$\epsilon$} (n);
-            \draw[->] (m) edge node {$\epsilon$} (n);
-        \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] (i) at (0, 0) {};
-
-            \node[state] (j) at (2.5, 0) {};
-            \node[state] (k) at (4, 0.5) {};
-            \node[state] (m) at (4, -0.5) {};
-
-            \node[state, accepting] (n) at (6.5, 0) {};
-
-            \draw[->] (i) edge node {$\epsilon$} (j);
-            \draw[->] (i) edge[bend right=90] node {$\epsilon$} (n);
-
-            \draw[->] (k) edge [bend right] node {$\epsilon$} (j);
-            \draw[->] (m) edge [bend left] node[above] {$\epsilon$} (j);
-            \draw[->] (k) edge node {$\epsilon$} (n);
-            \draw[->] (m) edge node {$\epsilon$} (n);
-        \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}{Potenzmengenkonstruktion}
-        Konstruiere einen Automaten, der \structure{alle möglichen Pfade} gleichzeitig berücksichtigt.
-        Gegeben ein NFA $(Q, \Sigma, \delta, S, F)$, konstruiere einen DFA mit Zuständen aus \alert{$\powerset{Q}$}.
-
-        \begin{itemize}
-            \item Starte in $\left\{ S \right\}$
-            \item Die Übergangsfunktion speichert \structure{alle möglichen Schritte}
-                \begin{align}
-                    \overline{\delta}: \powerset{Q} \times \Sigma &\to \powerset{Q} \\
-                    (M, a) &\mapsto \bigcup_{q \in M} \delta(q, a)
-                \end{align}
-            \item $M$ ist Endzustand wenn $F \cap M \neq \emptyset$
-        \end{itemize}
-    \end{block}
-
-    \begin{tikzpicture}[automaton, bend angle=20, node distance=2.1cm]
-        \tikzstyle{every state}=[minimum width=1cm, pretty]
-        \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 \structure{Äquivalenzrelation $\equiv_L \subseteq \Sigma^* \times \Sigma^*$}
-        \[ u \structure{\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 \structure{äquivalent} wenn sie die selbe Sprache akzeptieren.
-        \[ p \structure{\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 \structure{unterscheidbar}, wenn sie unterschiedliche Sprachen akzeptieren.
-        \[ p \structure{\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}
-}
-
-\defineUnit{quotientenautomat}{%
-\begin{frame}[t]
-    \frametitle{DFA minimieren}
-    \setbeamercovered{dynamic}
-
-    \begin{block}{Quotientenautomat}
-        \begin{enumerate}
-            \item Entferne alle von $q_0$ \alert{nicht erreichbaren} Zustände
-            \item<1, 3-> Berechne die \alert{unterscheidbaren} Zustände
-            \item<1, 6-> \alert{Kollabiere} die äquivalenten Zustände
-        \end{enumerate}
-    \end{block}
-
-    \vfill
-
-    \begin{columns}[c]<2->
-        \begin{column}{.5\textwidth}<3->
-            \begin{center}
-                \begin{tabu}to .8\textwidth{|X[c]|X[c]|X[c]|X}
-                    \multicolumn{2}{l}{0} \\ \tabucline{1-1}
-                    \alt<-4>{}{\textcolor{tumgreen}{$1/a$}} & \multicolumn{2}{l}{1} \\ \tabucline{1-2}
-                    \alt<-4>{}{\textcolor{tumgreen}{$1/a$}} &  & \multicolumn{2}{l}{2} \\ \tabucline{1-3}
-                    \alt<-3>{}{\textcolor{tumred}{$\times$}} &  \alt<-3>{}{\textcolor{tumred}{$\times$}}& \alt<-3>{} {\textcolor{tumred}{$\times$}}& 3 \\ \tabucline{1-3}
-                \end{tabu}
-            \end{center}
-        \end{column}
-        \begin{column}{.5\textwidth}
-            \begin{tikzpicture}[automaton, node distance=2.5cm]
-                \useasboundingbox (-0.5, -0.5) rectangle (2, -2);
-
-                \node[state, initial] (q0) {$q_0$};
-                \node<-5>[state] (q1) [right of = q0] {$q_1$};
-                \node<-5>[state] (q2) [below of = q0] {$q_2$};
-                \node<6>[state, fill=tumred!40] (q12) [right of = q0] {$q_{12}$};
-                \node[state, accepting] (q3) [right of = q2] {$q_3$};
-
-                \draw<-5>[->] (q0) edge node {$a$} (q1);
-                \draw<-5>[->] (q0) edge node {$b$} (q2);
-                \draw<-5>[->] (q1) edge node {$a,b$} (q3);
-                \draw<-5>[->] (q2) edge node {$a,b$} (q3);
-                \draw[->] (q3) edge [loop right] node [above] {$a,b$} (q3);
-
-                \draw<6>[->] (q12) edge node {$a,b$} (q3);
-                \draw<6>[->] (q0) edge node {$a,b$} (q12);
-            \end{tikzpicture}
-        \end{column}
-    \end{columns}
-\end{frame}
-}
-
-\defineUnit{regulaeresprachen}{%
-\begin{frame}
-    \frametitle{Reguläre Sprachen}
-    \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] (nfa) -- (dfa);
-            \draw [every edge] (enfa) -- (nfa);
-            \draw [every edge] (dfa) -- (re);
-            \draw [every edge] (nfa) -- (re);
-            \draw [every edge] (re) -- (enfa);
-        \end{tikzpicture}
-    \end{center}
-
-    \vfill
-
-    \begin{theorem}
-        Für eine Darstellung $D$ einer regulären Sprache ist \alert{entscheidbar}:
-        \vspace{1em}
-        \begin{description}
-            \item[Wortproblem] Gegeben $w$, gilt $w \in L(D)$?
-            \item[Leerheitsproblem] Ist $L(D) = \emptyset$?
-            \item[Endlichkeitsproblem] Ist $|L(D)| < \infty$?
-            \item[Äquivalenzproblem] Gilt $L(D_1) = L(D_2)$?
-        \end{description}
-    \end{theorem}
-\end{frame}
-}
diff -r d5b561a49683 -r 60757c0ba1f0 notes/tex/complete_notes.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/complete_notes.tex	Fri May 09 11:28:33 2014 +0200
@@ -0,0 +1,35 @@
+\input{preamble.tex}
+\input{frames.tex}
+
+\title{Übersichtsfolien zur Übung}
+\subtitle{Theoretische Informatik Sommersemester 2014}
+\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
+
+\begin{document}
+\showUnit{titel}
+
+%ue01
+\showUnit{organisatorisches}
+\showUnit{wasisttheo}
+\showUnit{alphabet}
+\showUnit{grammatik}
+\showUnit{sprachtypen}
+\showUnit{chomsky}
+\showUnit{berechenbarkeit}
+\showUnit{entscheidbarkeit}
+
+%ue02
+\showUnit{eindeutigkeit}
+\showUnit{dfa}
+\showUnit{nfa}
+\showUnit{enfa}
+\showUnit{nfazudfa}
+
+%ue03
+\showUnit{regex}
+\showUnit{rezuenfa}
+\showUnit{enfazunfa}
+\showUnit{aequivalentezustaende}
+\showUnit{unterscheidbarezustaende}
+\showUnit{quotientenautomat}
+\end{document}
diff -r d5b561a49683 -r 60757c0ba1f0 notes/tex/frames.tex
--- a/notes/tex/frames.tex	Mon May 05 14:41:06 2014 +0200
+++ b/notes/tex/frames.tex	Fri May 09 11:28:33 2014 +0200
@@ -98,6 +98,6 @@
 \end{frame}
 }
 
-\input{automatons.tex}
+\input{automata.tex}
 \input{grammars.tex}
 \input{computation.tex}