--- a/notes/tex/ue08_notes.tex	Thu Jul 11 21:57:50 2013 +0200
+++ b/notes/tex/ue08_notes.tex	Thu Jul 11 22:06:26 2013 +0200
@@ -1,184 +1,13 @@
 \input{preamble.tex}
+\input{frames.tex}
 
 \title{Übung 8: Turingmaschinen}
 \subtitle{Theoretische Informatik Sommersemester 2013}
 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
 
 \begin{document}
-
-\begin{frame}
-    \titlepage
-\end{frame}
-
-\begin{frame}
-    \frametitle{Kellerautomat}
-    \setbeamercovered{dynamic}
-
-    \begin{definition}[Kellerautomat]
-        Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem
-        \begin{itemize}
-
-            \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$
-        \end{itemize}
-    \end{definition}
-
-    \vfill
-
-    \begin{example}[]
-        PDA akzeptierend \alert{mit leerem Keller} zu $L = \left\{ a^nb^n \mid n \in \N \right\}$.
-
-        \centering
-        \begin{tikzpicture}[automaton]
-
-            \node[state, initial] (q0) {$q_0$};
-            \node[state] (q1) [right of = q0] {$q_1$};
-
-            \draw[->] (q0) edge [bend left] node {$\epsilon, A/A$} (q1);
-            \draw[->] (q0) edge [bend right] node [below] {$\epsilon, Z_0/Z_0$} (q1);
-
-            \draw[->] (q0) edge [loop above] node {$a, Z_0/AZ_0$} (q0);
-            \draw[->] (q0) edge [loop below] node {$a, A/AA$} (q0);
-
-            \draw[->] (q1) edge [loop above] node {$b, A/\epsilon$} (q1);
-            \draw[->] (q1) edge [loop below] node {$\epsilon, Z_0/\epsilon$} (q1);
-        \end{tikzpicture}
-    \end{example}
-\end{frame}
-
-\begin{frame}
-    \frametitle{Turingmaschinen}
-    \setbeamercovered{dynamic}
-
-    \begin{definition}[Turingmaschine]
-        Eine deterministische \alert{Turingmaschine (TM)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem
-        \begin{itemize}
-            \item endlichen Menge von \alert{Zuständen} $Q$
-            \item endlichen \alert{Eingabealphabet} $\Sigma$
-            \item endlichen \alert{Bandalphabet} $\Gamma$ mit $\Sigma \subset \Gamma$
-            \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$
-            \item \alert{Startzustand} $q_0 \in Q$
-            \item \alert{Leerzeichen} $\square \in \Gamma \setminus \Sigma$
-            \item Menge von \alert{Endzuständen} $F \subseteq Q$
-        \end{itemize}
-    \end{definition}
-\end{frame}
-
-\begin{frame}
-    \frametitle{Turingmaschinen}
-    \setbeamercovered{dynamic}
-
-    \begin{definition}[Turingmaschine]
-        Eine deterministische \alert{Turingmaschine (TM)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem
-        \begin{itemize}
-            \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$
-        \end{itemize}
-    \end{definition}
-
-    \vfill
-
-    \begin{center}
-        \begin{tikzpicture}
-            % Tape
-            \begin{scope}[start chain, node distance=0]
-                \node[on chain] {\ldots};
-                \node[tape] {$\square$};
-                \node[tape] (l) {$\square$};
-                \node[tape] {$0$};
-                \node[tape] {$1$};
-                \node<1>[tape, active] (a){$0$};
-                \node<2>[tape] (a){$1$};
-                \node<1>[tape] (b){$0$};
-                \node<2>[tape, active] (b){$0$};
-                \node[tape] {$\square$};
-                \node[on chain] {\ldots};
-            \end{scope}
-
-            % Head
-            \node<1> [head,yshift=-4mm] at (a.south) (head) {$q_0$};
-            \node<2> [head,yshift=-4mm] at (b.south) (head) {$q_1$};
-
-            % Machine
-            \node[machine, below=1.5cm of l] (machine) {Programm};
-            \draw[every edge] (machine) .. controls (3.5, -2) .. (head.south);
-
-            % Example-Transition
-            \node[yshift=5mm] at (current bounding box.north) {$\delta(q_0, 0) = (q_1, 1, R)$};
-        \end{tikzpicture}
-    \end{center}
-\end{frame}
-
-\begin{frame}
-    \frametitle{Turingmaschinen}
-    \setbeamercovered{dynamic}
-
-    \begin{definition}[Konfiguration]
-        Eine \alert{Konfiguration} ist ein Tripel $(\alpha, q, \beta) \in \Gamma^* \times Q \times \Gamma^*$. \\
-        Dies modelliert eine TM mit:
-        \begin{itemize}
-            \item \alert{Bandinhalt} $\ldots\square\alpha\beta\square\ldots$
-            \item \alert{Zustand} $q$
-            \item Kopf auf dem \alert{ersten Zeichen} von $\beta\square$
-        \end{itemize}
-        Die \alert{Startkonfiguration} bei Eingabe $w \in \Sigma^*$ ist $(\epsilon, q_0, w)$.
-    \end{definition}
-
-    \vfill
-
-    \only<1> {
-        \begin{center}
-            \begin{tikzpicture}
-            % Tape
-                \begin{scope}[start chain, node distance=0]
-                    \node[on chain] {\ldots};
-                    \node[tape] {$\square$};
-                    \node[tape] (l) {$\square$};
-                    \node[tape] {$0$};
-                    \node[tape] {$1$};
-                    \node[tape] (a){$1$};
-                    \node[tape, active] (b){$0$};
-                    \node[tape] {$\square$};
-                    \node[on chain] {\ldots};
-                \end{scope}
-
-            % Head
-                \node [head,yshift=-4mm] at (b.south) (head) {$q_1$};
-
-            % Machine
-                \node[below=1.5cm of l] (machine) {};
-                \draw[every edge, dashed] (machine) .. controls (3.5, -2) .. (head.south);
-
-            % Example-Transition
-                \node[yshift=5mm] at (current bounding box.north) {$(011,q_1,0)$};
-            \end{tikzpicture}
-        \end{center}
-    }
-
-    \only<2> {
-        \begin{definition}[Akzeptanz]
-            Eine TM $M$ \alert{akzeptiert} die Sprache
-            \[ L(M) = \left\{ w \in \Sigma^* \mid \exists \alert{f \in F}, \alpha, \beta \in \Gamma^* . (\epsilon, q_0, w) \rightarrow_M^* (\alpha, \alert{f}, \beta) \right\} \]
-        \end{definition}
-    }
-\end{frame}
-
-\begin{frame}
-    \frametitle{Nichtdeterministische TM}
-    \setbeamercovered{dynamic}
-
-    \begin{definition}[Nichtdeterministische Turingmaschine]
-        Eine \alert{nichtdeterministische} Turingmaschine (TM) ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem
-        \begin{itemize}
-            \item \ldots
-            \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to \mathcal{P} \left( Q \times \Gamma \times \left\{ L, R, N \right\} \right)$
-            \item \ldots
-        \end{itemize}
-    \end{definition}
-
-    \vfill
-
-    \begin{theorem}
-        Zu jeder nichtdeterministischen TM $N$ gibt es eine deterministische TM $M$ mit \alert{$L(N) = L(M)$}.
-    \end{theorem}
-\end{frame}
-
+\showUnit{titel}
+\showUnit{tmdefinition}
+\showUnit{tmvisualisierung}
+\showUnit{ndtm}
 \end{document}