--- a/notes/tex/preamble.tex	Tue Jun 11 16:21:06 2013 +0200
+++ b/notes/tex/preamble.tex	Mon Jun 17 23:59:22 2013 +0200
@@ -15,8 +15,9 @@
 \usepackage{pgfplots}
 \usetikzlibrary{automata}
 \usetikzlibrary{calc}
-\usetikzlibrary{shapes.geometric}
+\usetikzlibrary{shapes}
 \usetikzlibrary{positioning}
+\usetikzlibrary{chains}
 \usepackage{tabu}
 
 \usepackage{beamerthemeLEA2}
@@ -32,3 +33,8 @@
 \tikzstyle{every state} = [circle,thick,draw,fill=tumblue!10]
 \tikzstyle{automaton} = [shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=]
 \tikzstyle{small} = [every node/.style={scale=0.5}, baseline=(current bounding box.north), font=\LARGE]
+
+\tikzstyle{tape} = [on chain, draw, rectangle, minimum size = 6mm, fill=tumblue!10]
+\tikzstyle{active} = [fill=tumred!10]
+\tikzstyle{head} = [arrow box, draw, minimum size=5mm, arrow box arrows={east:.25cm, west:0.25cm, north:0.2cm}, fill=tumred!10]
+\tikzstyle{machine} = [rectangle, draw, minimum width=2cm, minimum height=1cm, inner sep=3mm, fill=tumgreen!10]

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/ue08_notes.tex	Mon Jun 17 23:59:22 2013 +0200
@@ -0,0 +1,184 @@
+\input{preamble.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 \mapsto 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 \mapsto 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 \mapsto 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 \mapsto \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}
+
+\end{document}

Binary file notes/ue08_notes.pdf has changed