--- a/notes/tex/grammars.tex	Sun May 11 00:27:30 2014 +0200
+++ b/notes/tex/grammars.tex	Wed May 14 21:30:04 2014 +0200
@@ -110,10 +110,12 @@
     \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.
+        Die \alert{induktive Definition} zu einer Grammatik $G$ ergibt sich direkt aus ihren Produktionen. Dabei werden kleinere Worte zu größeren Worten \alert{zusammengesetzt}, die Definition erfolgt \structure{bottom-up}.
     \end{block}
 
-    \begin{example}[Vorbereitung 3]
+    \vfill
+
+    \begin{example}
         Mit den Produktionen $S \rightarrow 0S1 \mid S11 \mid 1$:
 
         \begin{align*}
@@ -344,6 +346,34 @@
 \end{frame}
 }
 
+\defineUnit{ogden}{%
+\begin{frame}
+    \frametitle{Ogden Lemma für kontextfreie Sprachen}
+    \setbeamercovered{dynamic}
+
+    \begin{theorem}[Ogden Lemma für kontextfreie Sprachen]
+        Sei $L \subseteq \Sigma^*$ kontextfrei.\\
+        Dann gibt es ein $n > 0$, so dass für \alert{jedes} $z \in L$ mit $|z| \geq n$ gilt:\\
+        Für \alert{jede} Markierung $M$ von \alert{mindestens $n$} Buchstaben in $z$ gibt es eine Zerlegung $z = uvwxy$ mit
+        \begin{itemize}
+            \item $|vx|_M \alert{\geq 1}$
+            \item $|vwx|_M \alert{\leq n}$
+            \item $\forall i \alert{\geq 0}. uv^iwx^iy \in L$
+        \end{itemize}
+    \end{theorem}
+
+    \hfill
+
+    \begin{example}[Markierung]
+        Sei $w = abaabaaa$ ein Wort. Dann ist
+        \begin{align}
+            w = a\structure{ba}a\structure{b}aaa
+        \end{align}
+        eine Markierung mit $|w|_M = 3$.
+    \end{example}
+\end{frame}
+}
+
 \defineUnit{cyk}{%
 \begin{frame}
     \frametitle{CYK}
@@ -392,24 +422,34 @@
 \end{frame}
 }
 
+\defineUnit{greibach}{%
+\begin{frame}
+    \frametitle{Greibach Normalform}
+
+    Stuff.
+\end{frame}
+}
+
 \defineUnit{pda}{%
 \begin{frame}
     \frametitle{Kellerautomaten}
     \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
+        Ein \structure{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem
         \begin{itemize}
-            \item endlichen Menge von \alert{Zuständen} $Q$
-            \item endlichen \alert{Eingabealphabet} $\Sigma$
-            \item endlichen \alert{Kelleralphabet} $\Gamma$
-            \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$
-            \item \alert{Startzustand} $q_0 \in Q$
-            \item \alert{Kellerinitialisierung} $Z_0 \in \Gamma$
-            \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{Kelleralphabet} $\Gamma$
+            \item \structure{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$
+            \item \structure{Startzustand} $q_0 \in Q$
+            \item \structure{Kellerinitialisierung} $Z_0 \in \Gamma$
+            \item Menge von \structure{Endzuständen} $F \subseteq Q$
         \end{itemize}
     \end{definition}
 
+    \vfill
+
     \begin{center}
         \begin{tikzpicture}[automaton, node distance=4cm]
             \node[state] (q0) {$q_i$};
@@ -427,18 +467,18 @@
     \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
+        Ein \structure{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 \to P(Q \times \Gamma^*)$
+            \item \structure{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$
         \end{itemize}
     \end{definition}
 
     \vfill
 
     \begin{definition}[Akzeptanz]
-        Ein PDA $P$ akzeptiert $w \in \Sigma^*$ \alert{mit Endzustand} gdw
+        Ein PDA $P$ akzeptiert $w \in \Sigma^*$ \structure{mit Endzustand} gdw
         \[ \exists \alert{f \in F}, \gamma \in \Gamma^*.(q_0, w, Z_0) \rightarrow_P^* (\alert{f}, \epsilon, \gamma) \]
-        Ein PDA $P$ akzeptiert $w \in \Sigma^*$ \alert{mit leerem Keller} gdw
+        Ein PDA $P$ akzeptiert $w \in \Sigma^*$ \structure{mit leerem Keller} gdw
         \[ \exists q \in Q.(q_0, w, Z_0) \rightarrow_P^* (q, \epsilon, \alert{\epsilon}) \]
     \end{definition}
 \end{frame}
@@ -450,32 +490,34 @@
     \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
+        Ein \structure{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 \to P(Q \times \Gamma^*)$
+            \item \structure{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to 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\}$.
+        PDA akzeptierend \alert{mit leerem Keller} zu $L = \left\{ a^nb^n \mid n \in \N_0 \right\}$.
 
+        \bigskip
         \centering
         \begin{tikzpicture}[automaton]
 
             \node[state, initial] (q0) {$q_0$};
             \node[state] (q1) [right of = q0] {$q_1$};
+            \node[state] (q2) [right of = q1] {$q_2$};
 
-            \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 {$\epsilon, Z_0/\epsilon$};
 
-            \draw[->] (q0) edge [loop above] node {$a, Z_0/AZ_0$} (q0);
-            \draw[->] (q0) edge [loop below] node {$a, A/AA$} (q0);
+            \draw[->] (q0) edge node {$a, Z_0/AZ_0$} (q1);
+            \draw[->] (q1) edge node {$\epsilon, A/A$} (q2);
 
-            \draw[->] (q1) edge [loop above] node {$b, A/\epsilon$} (q1);
-            \draw[->] (q1) edge [loop below] node {$\epsilon, Z_0/\epsilon$} (q1);
+            \draw[->] (q1) edge [loop above] node {$a, */A*$} (q1);
+
+            \draw[->] (q2) edge [loop above] node {$b, */\epsilon$} (q2);
         \end{tikzpicture}
     \end{example}
 \end{frame}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/ue05_notes.tex	Wed May 14 21:30:04 2014 +0200
@@ -0,0 +1,16 @@
+\input{preamble.tex}
+\input{frames.tex}
+
+\title{Übung 5: Ogden-Lemma und Kellerautomaten}
+\subtitle{Theoretische Informatik Sommersemester 2014}
+\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
+
+\begin{document}
+\showUnit{titel}
+\showUnit{induktivesprachdefinition}
+\showUnit{ogden}
+\showUnit{greibach}
+\showUnit{pda}
+\showUnit{pdaakzeptanz}
+\showUnit{pdabeispiel}
+\end{document}