--- a/notes/tex/grammars.tex	Wed May 14 21:58:31 2014 +0200
+++ b/notes/tex/grammars.tex	Fri May 16 17:14:03 2014 +0200
@@ -424,9 +424,141 @@
 
 \defineUnit{greibach}{%
 \begin{frame}
-    \frametitle{Greibach Normalform}
+    \frametitle{Greibach-Normalform}
+
+    \begin{definition}[Greibach-Normalform]
+        Eine kontextfreie Grammatik ist in \structure{Greibach-Normalform} (GNF) genau dann wenn alle Produktionen außer $S \to \epsilon$ die Form
+        \[
+            A \rightarrow \alert{a\alpha} \quad \text{mit} \quad a \in \Sigma, \alpha \in V^*
+        \]
+        haben.
+    \end{definition}
+
+    \vfill
+
+    \begin{theorem}
+        Zu \alert{jeder} CFG $G$ existiert eine CFG $G'$ in Greibach-Normalform mit
+        \[
+            L(G') = L(G)
+        \]
+    \end{theorem}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Einsetzen von Produktionen}
+
+    \begin{theorem}[Einsetzen von Produktionen]
+        Enthält eine CFG die Produktionen
+        \begin{align}
+            A &\to \alpha_1 \structure{B} \alpha_2\\
+            \structure{B} &\to \alert{\beta_1} \mid \dots \mid \alert{\beta_k}
+            \intertext{so ändert sich die erzeugte Sprache nicht, wenn man $B$ in $A$ \structure{einsetzt}.}
+            A &\to \alpha_1 \alert{\beta_1} \alpha_2 \mid \dots \mid \alpha_1 \alert{\beta_k} \alpha_2
+        \end{align}
+    \end{theorem}
+
+    \vfill
+
+    \begin{example}
+        Die Grammatik
+        \begin{align}
+            S &\to a \mid a\structure{B}c \\
+            \structure{B} &\to \alert{b} \mid \alert{bS}
+            \intertext{ist äquivalent zur Grammatik}
+            S &\to a \mid a\alert{b}c \mid a\alert{bS}c
+        \end{align}
+    \end{example}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Linksrekursive Produktionen}
+
+    \begin{definition}[Linksrekursive Produktion]
+        Man nennt eine Produktion \structure{linksrekursiv}, wenn sie die Form
+        \[
+            \structure{A} \to \structure{A}\alpha_1 \mid \dots \mid \structure{A}\alpha_k \mid \beta_i \mid \dots \mid \beta_l \quad \text{mit} \quad \alpha_i, \beta_i \in \left( V \cup \Sigma \right)^+
+        \]
+        hat, wobei die $\beta_i$ nicht mit $A$ beginnen.
+    \end{definition}
+
+    \vfill
 
-    Stuff.
+    \begin{theorem}[Ersetzen von linksrekursiven Produktionen]
+        Sei $A$ eine linksrekursive Produktion einer CFG.\\
+        Dann ändert sich die erzeugte Sprache nicht, wenn wir $A$ \structure{ersetzen} durch
+        \begin{align}
+            \structure{A} &\to \beta_1 \mid \dots \mid \beta_l \mid \beta_1 \alert{B} \mid \dots \mid \beta_l \alert{B}\\
+            \alert{B} &\to \alpha_1 \mid \dots \mid \alpha_k \mid \alpha_1 \alert{B} \mid \dots \mid \alpha_k \alert{B}
+        \end{align}
+        \alert{$B$} ist niemals linksrekursiv.
+    \end{theorem}
+\end{frame}
+}
+
+\defineUnit{greibachkonstruktion}{%
+\begin{frame}
+    \frametitle{GNF Konstruktion}
+
+    \begin{block}{GNF Konstruktion}
+        Sei $G = (V, \Sigma, P, S)$ eine CFG.
+        \begin{enumerate}
+            \item<1,2-> \alert{Nummeriere} Nichtterminale
+            \item<1,3-> Mache Prduktionen \alert{aufsteigend} und \alert{nicht rekursiv}
+            \item<1,5-> \alert{Setze} Produktionen absteigend \alert{ein}
+        \end{enumerate}
+    \end{block}
+
+    \vspace{1em}
+
+    \only<2> {
+        Benenne alle Nichtterminale \structure{beliebig} um in $A_1, \dots, A_\abs{V}$.
+        \begin{align}
+            S &\rightarrow Ab, \quad A \rightarrow aAS \mid \epsilon \\
+            \intertext{wird zu}
+            A_1 &\to A_2b\\
+            A_2 &\to aA_2A_1
+        \end{align}
+    }
+
+    \only<3,4> {
+        Betrachte alle Produktionen $A_l \to \dots$ in \structure{aufsteigender Reihenfolge}.\\
+        \begin{itemize}
+            \item Existieren Produktionen der Form $A_l \to \structure{A_r}\alpha$ mit \alert{$r < l$}, dann setze \structure{$A_r$} in $A_l$ ein.
+                \only<3> {
+                    \begin{align}
+                        A_1 &\to A_2 \mid a \mid b \\
+                        A_2 &\to \structure{A_1}xA_1
+                        \intertext{wird zu}
+                        A_1 &\to a \mid b\\
+                        A_2 &\to \structure{A_2}xA_1 \mid \structure{a}xA_1 \mid \structure{b}xA_1
+                    \end{align}
+                }
+            \item Entferne danach alle \structure{linksrekursiven} $A_l$-Produktionen.
+                \only<4> {
+                    \begin{align}
+                        A_2 &\to A_2\structure{xA_1} \mid \alert{axA_1} \mid \alert{bxA_1}
+                        \intertext{wird zu}
+                        A_2 &\to \alert{axA_1} \mid \alert{bxA_1} \mid \alert{axA_1}A_3 \mid \alert{bxA_1}A_3\\
+                        A_3 &\to \structure{xA_1} \mid \structure{xA_1}A_3
+                    \end{align}
+                }
+        \end{itemize}
+    }
+
+    \only<5> {
+        Betrachte alle Produktionen $A_l \to \dots$ in \structure{absteigender Reihenfolge}.\\
+        \begin{itemize}
+            \item Existieren Produktionen der Form $A_l \to \structure{A_r}\alpha$ mit \alert{$r > l$}, dann setze \structure{$A_r$} in $A_l$ ein.
+                \begin{align}
+                        A_1 &\to a \mid b \mid \structure{A_2} \\
+                        A_2 &\to axA_1 \mid bxA_1 \mid axA_1A_3 \mid bxA_1A_3\\
+                        A_3 &\to xA_1 \mid xA_1A_3
+                        \intertext{$A_1$ wird zu}
+                        A_1 &\to a \mid b \mid \structure{axA_1} \mid \structure{bxA_1} \mid \structure{axA_1A_3} \mid \structure{bxA_1A_3}
+                \end{align}
+        \end{itemize}
+
+    }
 \end{frame}
 }
 
@@ -510,7 +642,7 @@
             \node[state] (q1) [right of = q0] {$q_1$};
             \node[state] (q2) [right of = q1] {$q_2$};
 
-            \draw[->] (q0) edge [loop above] node {$\epsilon, Z_0/\epsilon$};
+            \draw[->] (q0) edge [loop above] node {$\epsilon, Z_0/\epsilon$} (q0);
 
             \draw[->] (q0) edge node {$a, Z_0/AZ_0$} (q1);
             \draw[->] (q1) edge node {$\epsilon, A/A$} (q2);

--- a/notes/tex/ue05_notes.tex	Wed May 14 21:58:31 2014 +0200
+++ b/notes/tex/ue05_notes.tex	Fri May 16 17:14:03 2014 +0200
@@ -10,6 +10,7 @@
 \showUnit{induktivesprachdefinition}
 \showUnit{ogden}
 \showUnit{greibach}
+\showUnit{greibachkonstruktion}
 \showUnit{pda}
 \showUnit{pdaakzeptanz}
 \showUnit{pdabeispiel}

Binary file notes/ue05_notes.pdf has changed

Binary file ue05.pdf has changed