--- a/notes/tex/automatons.tex	Thu Jul 11 21:25:21 2013 +0200
+++ b/notes/tex/automatons.tex	Thu Jul 11 21:57:50 2013 +0200
@@ -170,7 +170,7 @@
 \end{frame}
 }
 
-\defineUnit{rezunfa}{%
+\defineUnit{rezuenfa}{%
 \begin{frame}
     \frametitle{RE $\rightarrow$ $\epsilon$-NFA}
     \setbeamercovered{dynamic}
@@ -365,17 +365,18 @@
 
 \defineUnit{produktautomat}{%
 \begin{frame}
-    \frametitle{produktautomat}
+    \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}
+        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) \\
+            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.
+        ein DFA, der $L(M_1) \cap L(M_2)$ akzeptiert.
     \end{theorem}
 \end{frame}
 }
@@ -526,7 +527,7 @@
 \end{frame}
 }
 
-\defineUnit{aequivalenteZustaende}{%
+\defineUnit{aequivalentezustaende}{%
 \begin{frame}
     \frametitle{Äquivalenzen}
     \setbeamercovered{dynamic}
@@ -552,7 +553,7 @@
 \end{frame}
 }
 
-\defineUnit{unterscheidbareZustaende}{%
+\defineUnit{unterscheidbarezustaende}{%
 \begin{frame}
     \frametitle{Unterscheidbare Zustände}
     \setbeamercovered{dynamic}
@@ -593,3 +594,90 @@
     \end{tikzpicture}
 \end{frame}
 }
+
+\defineUnit{quotientenautomat}{%
+\begin{frame}[t]
+    \frametitle{DFA minimieren}
+    \setbeamercovered{dynamic}
+
+    \begin{block}{Idee}
+        Erzeuge den \alert{Quotientenautomaten}.
+        \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
+    \pause
+
+    \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}
+}