--- a/notes/tex/computation.tex	Sun Jun 01 00:30:12 2014 +0200
+++ b/notes/tex/computation.tex	Fri Jun 06 17:13:58 2014 +0200
@@ -4,15 +4,15 @@
     \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
+        Eine deterministische \structure{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$
+            \item endlichen Menge von \structure{Zuständen} $Q$
+            \item endlichen \structure{Eingabealphabet} $\Sigma$
+            \item endlichen \structure{Bandalphabet} $\Gamma$ mit $\Sigma \subset \Gamma$
+            \item \structure{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$
+            \item \structure{Startzustand} $q_0 \in Q$
+            \item \structure{Leerzeichen} $\square \in \Gamma \setminus \Sigma$
+            \item Menge von \structure{Endzuständen} $F \subseteq Q$
         \end{itemize}
     \end{definition}
 \end{frame}
@@ -24,9 +24,9 @@
     \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
+        Eine deterministische \structure{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\}$
+            \item \structure{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$
         \end{itemize}
     \end{definition}
 
@@ -70,14 +70,14 @@
     \setbeamercovered{dynamic}
 
     \begin{definition}[Konfiguration]
-        Eine \alert{Konfiguration} ist ein Tripel $(\alpha, q, \beta) \in \Gamma^* \times Q \times \Gamma^*$. \\
+        Eine \structure{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$
+            \item \structure{Bandinhalt} $\ldots\square\alpha\beta\square\ldots$
+            \item \structure{Zustand} $q$
+            \item Kopf auf dem \structure{ersten Zeichen} von $\beta\square$
         \end{itemize}
-        Die \alert{Startkonfiguration} bei Eingabe $w \in \Sigma^*$ ist $(\epsilon, q_0, w)$.
+        Die \structure{Startkonfiguration} bei Eingabe $w \in \Sigma^*$ ist $(\epsilon, q_0, w)$.
     \end{definition}
 
     \vfill
@@ -113,7 +113,7 @@
 
     \only<2> {
         \begin{definition}[Akzeptanz]
-            Eine TM $M$ \alert{akzeptiert} die Sprache
+            Eine TM $M$ \structure{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}
     }
@@ -126,10 +126,10 @@
     \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
+        Eine \structure{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 \structure{Ü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}
@@ -142,6 +142,22 @@
 \end{frame}
 }
 
+\defineUnit{lba}{%
+\begin{frame}
+    \frametitle{Linear Beschränkte Automaten}
+
+    \begin{definition}[Linear Beschränkte Automaten]
+        Eine TM heißt \structure{linear beschränkt (LBA)}, wenn sie den Bereich des Bandes, auf dem das Eingabewort steht, niemals verlässt.
+    \end{definition}
+
+    \vfill
+
+    \begin{theorem}[]
+        Die \structure{linear beschränkten NDTMs} akzeptieren genau die Klasse der \alert{kontextsensitiven Sprachen (Typ 1)}.
+    \end{theorem}
+\end{frame}
+}
+
 \defineUnit{chomsky}{%
 \begin{frame}[c]
     \frametitle{Chomsky-Hierarchie}
@@ -153,10 +169,10 @@
             \tikzstyle{caption} = [align=left, anchor=north west];
 
             \chomsky{tumlightblue}{}{0}{Alle formalen Sprachen};
-            \chomsky{tumred}{}{1}{Typ 0 - Rekursiv aufzählbar\\Grammatik};
-            \chomsky{tumblue}{}{2}{Typ 1 - Kontextsensitiv\\Längenmonotone Grammatik};
-            \chomsky{tumorange}{}{3}{Typ 2 - Kontextfrei\\Links nur ein Nichtterminal};
-            \chomsky{tumgreen}{}{4}{Typ 3 - Regulär\\Links- / Rechtsreguläre Grammatik};
+            \chomsky{tumred}{}{1}{Typ 0 - Rekursiv aufzählbar\\Grammatik\\Turingmaschine, WHILE-Programm, $\mu$-rekursive Funktion};
+            \chomsky{tumblue}{}{2}{Typ 1 - Kontextsensitiv\\Längenmonotone Grammatik\\Linear Beschränkter Automat (LBA)};
+            \chomsky{tumorange}{}{3}{Typ 2 - Kontextfrei\\Links nur ein Nichtterminal\\Kellerautomat (PDA)};
+            \chomsky{tumgreen}{}{4}{Typ 3 - Regulär\\Links- / Rechtsreguläre Grammatik\\DFA, NFA, RE};
         \end{tikzpicture}
     \end{center}
 \end{frame}
@@ -954,14 +970,14 @@
     \vfill
 
     \begin{theorem}[]
-        Sei $A$ formale Sprache, dann ist äuqivalent:
+        Sei $A$ formale Sprache, dann ist äquivalent:
         \vspace{1em}
         \begin{itemize}
-            \item $A$ ist \alert{Typ 0 Sprache}
-            \item $A$ \alert{rekursiv aufzählbar}
-            \item $A$ \alert{semi-entscheidbar}, also $\chi'_A$ berechenbar
-            \item $A=L(M)$ für eine \alert{TM $M$}
-            \item $A$ ist \alert{Bild oder Urbild} einer berechenbaren Funktion
+            \item $A$ ist \structure{Typ 0 Sprache}
+            \item $A$ \structure{rekursiv aufzählbar}
+            \item $A$ \structure{semi-entscheidbar}, also $\chi'_A$ berechenbar
+            \item $A=L(M)$ für eine \structure{TM $M$}
+            \item $A$ ist \structure{Bild oder Urbild} einer berechenbaren Funktion
         \end{itemize}
     \end{theorem}
 \end{frame}
@@ -973,13 +989,14 @@
     \setbeamercovered{dynamic}
 
     \begin{itemize}
-        \item \alert{Abschlusseigenschaften}
+        \item Abschlusseigenschaften
     \end{itemize}
     \begin{table}
         \begin{tabu}to \textwidth{X[c]|ccccc}
             & Schnitt & Vereinigung & Komplement & Produkt & Stern \\ \tabucline{}
             REG & ja & ja & ja & ja & ja\\
             CFL & nein & ja & nein & ja & ja\\
+            CSL & ja & ja & ja & ja & ja\\
             TM & \structure{ja} & \structure{ja} & \structure{nein} & \structure{ja} & \structure{ja}
         \end{tabu}
     \end{table}
@@ -987,13 +1004,14 @@
     \vfill
 
     \begin{itemize}
-        \item \alert{Entscheidbarkeit}
+        \item Entscheidbarkeit
     \end{itemize}
     \begin{table}
         \begin{tabu}to \textwidth{X[c]|cccc}
             & Wortproblem & Leerheit & Äquivalenz & Schnittproblem\\ \tabucline{}
             DFA & $\Oh(n)$ & ja & ja & ja\\
             CFG & $\Oh(n^3)$ & ja & nein & nein\\
+            CSL & $\Oh(2^n)$ & nein & nein & nein\\
             TM & \structure{nein} & \structure{nein} & \structure{nein} & \structure{nein}
         \end{tabu}
     \end{table}
@@ -1010,12 +1028,13 @@
             \tikzstyle{rect} = [thick];
             \tikzstyle{caption} = [align=left, anchor=north west];
 
-            \langclass{brown}{}{0}{Formale Sprache - $\Sigma^*$};
+            \definecolor{hannahyellow}{HTML}{FFB81C}
+            \langclass{brown}{}{0}{Formale Sprache $\subseteq \Sigma^*$};
             \langclass{tumblue}{}{1}{Typ 0 - Semi-Entscheidbar};
             \langclass{tumgreen}{}{2}{Entscheidbar};
             \langclass{violet}{}{3}{LOOP, PR};
             \langclass{tumred}{}{4}{NP};
-            \langclass{tumorange}{dashed}{5}{P};
+            \langclass{hannahyellow}{dashed}{5}{P};
             \langclass{tumgreen!40!black}{}{6}{Typ 2 - Kontextfrei};
             \langclass{tumlightblue!80!black}{}{7}{Typ 3 - Regulär};
             \langclass{tumblue!20!black}{}{8}{Endlich};