--- a/notes/tex/grammars.tex	Thu Jul 11 21:25:21 2013 +0200
+++ b/notes/tex/grammars.tex	Thu Jul 11 21:57:50 2013 +0200
@@ -64,6 +64,33 @@
 \end{frame} 
 }
 
+\defineUnit{induktivesprachdefinition}{%
+\begin{frame}
+    \frametitle{Induktive Sprachdefinition}
+    \setbeamercovered{dynamic}
+
+    \begin{block}{Induktive Sprachdefinition}
+        Die \alert{induktive Definition} ($\Longrightarrow$) erzeugt Wörter \alert{bottom-up}, setzt also kleine Wörter zu größeren zusammen.
+    \end{block}
+
+    \begin{example}[Vorbereitung 3]
+        Mit den Produktionen $S \rightarrow 0S1 \mid S11 \mid 1$:
+
+        \begin{align*}
+            1 &\in L_G(S) \\
+            u \in L_G(S) \quad \Longrightarrow \quad 0\alert{u}1 &\in L_G(S) \\
+            u \in L_G(S) \quad \Longrightarrow \quad \alert{u}11 &\in L_G(S)
+        \end{align*}
+
+        Also z.B:
+
+        \[
+            1 \in L_G(S) \Longrightarrow 0\alert{1}0 \in L_G(S) \Longrightarrow \alert{010}11 \in L_G(S)
+        \]
+    \end{example}
+\end{frame}
+}
+
 \defineUnit{cnf}{%
 \begin{frame}
     \frametitle{CNF}
@@ -173,6 +200,76 @@
 \end{frame}
 }
 
+\defineUnit{cfpl}{%
+\begin{frame}
+    \frametitle{Pumping Lemma für CFLs}
+    \setbeamercovered{dynamic}
+
+    \begin{theorem}[Pumping Lemma für kontextfreie Sprachen]
+        Sei $L \subseteq \Sigma^*$ kontextfrei. Dann gibt es ein $n > 0$, so dass sich \alert{jedes} $z \in L$ mit $|z| \geq n$ so in \alert{$z = uvwxy$} zerlegen lässt, dass
+        \begin{itemize}
+            \item $vx \alert{\neq \epsilon}$
+            \item $|vwx| \alert{\leq n}$
+            \item $\forall i \alert{\geq 0}. uv^iwx^iy \in L$
+        \end{itemize}
+    \end{theorem}
+
+    \vfill
+
+    \begin{center}
+        \begin{columns}
+            \begin{column}{.4\textwidth}
+                \begin{tikzpicture}
+                    \coordinate (outer) at (2, 2.4);
+                    \coordinate (middle) at (2.2, 1.2);
+                    \coordinate (inner) at (2.2, 0.6);
+                    % outer
+                    \draw[fill=tumred!40] (0, 0) -- (1.2, 0) -- (middle) -- (3.2, 0) -- (4, 0) -- (outer) node[above] {$S$} -- (0, 0);
+                    % middle
+                    \draw[fill=tumgreen!40] (1.2, 0) -- (1.7, 0) -- (inner) -- (2.7, 0) -- (3.2, 0) -- (middle) -- (1.2, 0);
+                    % inner
+                    \draw[fill=tumblue!40] (1.7, 0) -- (inner) -- (2.7, 0) -- (1.7, 0);
+
+                    % path
+                    \draw[dashed, thick] (outer) -- (middle) -- (inner);
+                    \draw[fill] (outer) circle (1pt);
+                    \draw[fill] (middle) circle (1pt);
+                    \draw[fill] (inner) circle (1pt);
+
+                    % nodes
+                    \node[below] at (0.6, 0) {$u$};
+                    \node[below] at (1.45, 0) {$v$};
+                    \node[below] at (2.2, 0) {$w$};
+                    \node[below] at (2.95, 0) {$x$};
+                    \node[below] at (3.6, 0) {$y$};
+                \end{tikzpicture}
+            \end{column}
+            \begin{column}{.4\textwidth}
+                \begin{tikzpicture}
+                    \coordinate (outer) at (2, 2.4);
+                    \coordinate (middle) at (2.2, 1.2);
+                    \coordinate (inner) at (2.2, 0.6);
+                    % outer
+                    \draw[fill=tumred!40] (0, 0) -- (1.2, 0) -- (middle) -- (3.2, 0) -- (4, 0) -- (outer) node[above] {$S$} -- (0, 0);
+                    % inner
+                    \draw[fill=tumblue!40] (1.7, 0.6) -- (middle) -- (2.7, 0.6) -- (1.7, 0.6);
+
+                    % path
+                    \draw[dashed, thick] (outer) -- (middle);
+                    \draw[fill] (outer) circle (1pt);
+                    \draw[fill] (middle) circle (1pt);
+
+                    % nodes
+                    \node[below] at (0.6, 0) {$u$};
+                    \node[below] at (2.2, 0) {$w$};
+                    \node[below] at (3.6, 0) {$y$};
+                \end{tikzpicture}
+            \end{column}
+        \end{columns}
+    \end{center}
+\end{frame}
+}
+
 \defineUnit{cyk}{%
 \begin{frame}
     \frametitle{CYK}
@@ -308,3 +405,48 @@
     \end{example}
 \end{frame}
 }
+
+\defineUnit{kontextfreiesprachen}{%
+\begin{frame}
+    \frametitle{Kontextfreie Sprachen}
+    \setbeamercovered{dynamic}
+
+    \begin{center}
+        \begin{tikzpicture}[node distance=3cm]
+            \node (CFG) {CFG};
+            \node (CNF) [right of = CFG] {CNF};
+            \node (PDAe) [right of = CNF] {PDA$_\epsilon$};
+            \node (PDAf) [right of = PDAe] {PDA$_F$};
+
+            \draw [every edge, <->] (CFG) -- (CNF);
+            \draw [every edge, <->] (CNF) -- (PDAe);
+            \draw [every edge, <->] (PDAe) -- (PDAf);
+        \end{tikzpicture}
+    \end{center}
+
+    \pause
+    \vfill
+
+    \begin{itemize}
+        \item \alert{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 
+        \end{tabu}
+    \end{table}
+
+    \begin{itemize}
+        \item \alert{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
+        \end{tabu}
+    \end{table}
+\end{frame}
+}