--- a/notes/tex/grammars.tex	Sun Apr 13 17:11:29 2014 +0200
+++ b/notes/tex/grammars.tex	Sun Apr 13 20:22:34 2014 +0200
@@ -3,22 +3,26 @@
     \frametitle{Grammatiken}
     \setbeamercovered{dynamic}
 
-    \begin{definition}[Kontextfreie Grammatik]
-        Eine \alert{kontextfreie Grammatik} $G = (V, \Sigma, P, S)$ ist ein 4-Tupel:
+    \begin{definition}[Grammatik]
+        Eine \structure{(Phrasenstruktur-)Grammatik} $G = (V, \Sigma, P, S)$ ist ein 4-Tupel:
         \begin{description}
             \item[V] endlich viele \alert{Nichtterminale} (Variablen)
             \item[$\Sigma$] ein Alphabet von \alert{Terminalen}
-            \item[P] endlich viele \alert{Produktionen} $\subseteq V \times \left( V \cup \Sigma \right)^*$
-            \item[S] ein \alert{Startsymbol}
+            \item[P] endlich viele \alert{Produktionen} $\subseteq \left( V \cup \Sigma \right)^* \times \left( V \cup \Sigma \right)^*$
+            \item[S] ein \alert{Startsymbol} (Axiom)
         \end{description}
+        Ist $(l, r) \in P$, so schreibt man \structure{$l \rightarrow r$}.
     \end{definition}
 
-    \begin{example}[Vorbereitung 3]
+    \vfill
+
+    \begin{example}[]
         $\Sigma = \left\{ 0, 1 \right\}$. Grammatik für alle Wörter ungerader Länge, bei denen alle Nullen vor der ersten Eins stehen und weniger Nullen als Einsen vorhanden sind.
-        \pause
-        \[
-            S \rightarrow 0S1 \mid S11 \mid 1
-        \]
+        \visible<2>{
+            \begin{align}
+                S \rightarrow 0S1 \mid S11 \mid 1
+            \end{align}
+        }
     \end{example}
 \end{frame}
 }
@@ -29,26 +33,62 @@
     \setbeamercovered{dynamic}
 
     \begin{definition}[Ableitungsrelation]
-        Eine CFG $G$ induziert eine \alert{Ableitungsrelation} $\rightarrow_G$ auf Wörtern über $V \cup \Sigma$:
-        \[
-            \alpha \rightarrow_G \beta
-        \]
-        gdw es eine Regel $A \rightarrow \gamma$ in $P$ mit Wörtern $\alpha_1, \alpha_2$ gibt, so dass
-        \[
-            \alpha = \alpha_1\alert{A}\alpha_2 \quad \text{und} \quad \beta = \alpha_1 \alert{\gamma} \alpha_2
-        \]
+        Eine Grammatik $G$ induziert eine \structure{Ableitungsrelation} $\rightarrow_G$ auf Wörtern über $V \cup \Sigma$. Seien $x, y$ solche Wörter und
+        \begin{align}
+            z &= x\alert{\alpha}y\\
+            z^\prime &= x\alert{\beta}y\\
+            \intertext{Dann ist}
+            z &\rightarrow_G z^\prime
+        \end{align}
+        gdw. es eine Regel $\alert{\alpha \rightarrow \beta}$ in $P$ gibt.
     \end{definition}
 
-    \begin{example}[Vorbereitung 3]
+    \vfill
+
+    \begin{example}[]
         Mit den Produktionen $S \rightarrow 0S1 \mid S11 \mid 1$:
         \begin{align*}
             S &\rightarrow_G 0S1 \rightarrow_G 00S11 \rightarrow_G 00S1111 \rightarrow_G 0011111 \\
-            \Rightarrow S &\rightarrow_G^* 0011111
+            \intertext{Es gilt also}
+            S &\rightarrow_G^* 0011111
         \end{align*}
     \end{example}
 \end{frame}
 }
 
+\defineUnit{sprachtypen}{%
+\begin{frame}
+    \frametitle{Sprachtypen}
+
+    Sei $G = (V, \Sigma, P, S)$ eine Grammatik und $\alpha \rightarrow \beta \in P$ beliebig.
+    \begin{definition}[Monotonie]
+        $G$ heißt \structure{(längen-)monoton}, wenn für $\alpha \neq S$ gilt
+        \begin{align}
+            \alert{\abs{\alpha} \leq \abs{\beta}}
+        \end{align}
+        und falls $S \to \epsilon \in P$, dann kommt $S$ nie auf der rechten Seite vor.
+    \end{definition}
+
+    \vfill
+
+    \begin{definition}[Chomsky-Typen]
+        Seien $A \in V$, $\gamma, \delta \in (V \cup \Sigma)^*$ und $\beta^\prime \in (V \cup \Sigma)^+$.\\
+        Damit $G$ vom \structure{Typ k} ist, muss für $\alpha$ und $\beta$ gelten
+        \begin{center}
+            \tabulinesep=4pt
+            \begin{tabu} to .8\textwidth{X[1,c,m]|[.5pt]X[2,c,m]X[2,c,m]}
+                & $\alpha$ & $\beta$\\\tabucline[.5pt]{-}
+                \structure{Typ 0} & beliebig & beliebig\\
+                \structure{Typ 1} & $= \alert{\gamma} A \alert{\delta}$ & $= \alert{\gamma} \beta^\prime \alert{\delta}$\\
+                \structure{Typ 2} & $\in V$ & beliebig\\
+                \structure{Typ 3} & $\in V$ & $\in \Sigma^+ \cup \Sigma^*V$\\
+            \end{tabu}
+        \end{center}
+        Ab Typ 1 muss $G$ auch \alert{monoton} sein.
+    \end{definition}
+\end{frame}
+}
+
 \defineUnit{cfl}{%
 \begin{frame}[c]
     \frametitle{Kontextfreie Sprache}