--- a/notes/tex/ue07_notes.tex	Thu Jul 11 21:57:50 2013 +0200
+++ b/notes/tex/ue07_notes.tex	Thu Jul 11 22:06:26 2013 +0200
@@ -1,183 +1,15 @@
 \input{preamble.tex}
+\input{frames.tex}
 
 \title{Übung 7: CYK und Kellerautomaten}
 \subtitle{Theoretische Informatik Sommersemester 2013}
 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
 
 \begin{document}
-
-\begin{frame}
-    \titlepage
-\end{frame}
-
-\begin{frame}
-    \frametitle{CYK}
-    \setbeamercovered{dynamic}
-
-    \begin{definition}[Cocke-Younger-Kasami-Algorithmus]
-        Der \alert{CYK-Algorithmus} entscheidet das Wortproblem für kontextfreie Grammatiken in Chomsky-Normalform in $\Oh(n^3)$. \\
-        Gegeben eine \alert{Grammatik} $G = (V, \Sigma, P, S)$ in CNF und ein \alert{Wort} $w = a_1 \ldots a_n \in \Sigma^*$.
-        Mit \[ V_{ij} := \left\{ A \in V \mid A \rightarrow_G^* \alert{a_i \ldots a_j} \right\}\]
-        ist \[ w \in L(G) \Leftrightarrow S \in V_{\alert{1n}} \]
-    \end{definition}
-
-    \begin{align*}
-        V_{ii} &= \left\{ A \in V \mid (A \rightarrow a_i) \in P \right\} \\
-        V_{ij} &= \left\{ A \in V \mid \exists k, B \in V_{ik}, C \in V_{k+1,j} \;.\; (A \rightarrow BC) \in P \right\}
-    \end{align*}
-
-\end{frame}
-
-\begin{frame}
-    \frametitle{CYK}
-    \setbeamercovered{dynamic}
-
-    \begin{block}{Idee}
-        Kombiniere \alert{Teilwörter} zum ganzen Wort, wenn möglich.
-        \begin{enumerate}
-            \item Initialisiere mit den \alert{$V_{ii}$}.
-            \item<3-5> Befülle die Tabelle von unten nach oben.
-        \end{enumerate}
-    \end{block}
-
-    \[ S \rightarrow AB \mid BC, \quad A \rightarrow BA \mid a, \quad B \rightarrow CC \mid b, \quad C \rightarrow AB \mid a \]
-    \begin{center}
-        \extrarowsep=5pt
-        \begin{tabu}to .8\textwidth{r|X[c]|X[c]|X[c]|X[c]|}
-            \tabucline{2-2}
-            4 & \alt<-4>{}{$S,\ldots$} \\ \tabucline{2-3}
-            3 & \alt<-3>{}{$\emptyset$} & \alt<-3>{}{$S, A, C$} \\ \tabucline{2-4}
-            2 & \alt<-2>{}{$A$} & \alt<-2>{}{$B$} & \alt<-2>{}{$B$} \\ \tabucline{2-5}
-            1 & \alt<-1>{}{$B$} & \alt<1>{}{$A,C$} & \alt<1>{}{$A,C$} & \alt<1>{}{$A,C$} \\ \tabucline{2-5}
-            \multicolumn{1}{r}{} & \multicolumn{1}{c}{\alert{b}} & \multicolumn{1}{c}{\alert{a}} & \multicolumn{1}{c}{\alert{a}} & \multicolumn{1}{c}{\alert{a}} \\
-        \end{tabu}
-    \end{center}
-\end{frame}
-
-\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
-        \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$
-        \end{itemize}
-    \end{definition}
-
-    \begin{center}
-        \begin{tikzpicture}[automaton, node distance=4cm]
-            \node[state] (q0) {$q_i$};
-            \node[state] (q1) [right of = q0] {$q_j$};
-
-            \draw[every edge] (q0) edge node {$a, X/\gamma$} (q1);
-        \end{tikzpicture}
-    \end{center}
-\end{frame}
-
-\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
-        \begin{itemize}
-            \item \alert{Ü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
-        \[ \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
-        \[ \exists q \in Q.(q_0, w, Z_0) \rightarrow_P^* (q, \epsilon, \alert{\epsilon}) \]
-    \end{definition}
-\end{frame}
-
-\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
-        \begin{itemize}
-
-            \item \alert{Ü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\}$.
-
-        \centering
-        \begin{tikzpicture}[automaton]
-
-            \node[state, initial] (q0) {$q_0$};
-            \node[state] (q1) [right of = q0] {$q_1$};
-
-            \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 {$a, Z_0/AZ_0$} (q0);
-            \draw[->] (q0) edge [loop below] node {$a, A/AA$} (q0);
-
-            \draw[->] (q1) edge [loop above] node {$b, A/\epsilon$} (q1);
-            \draw[->] (q1) edge [loop below] node {$\epsilon, Z_0/\epsilon$} (q1);
-        \end{tikzpicture}
-    \end{example}
-\end{frame}
-
-\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}
-
+\showUnit{titel}
+\showUnit{cyk}
+\showUnit{cykbeispiel}
+\showUnit{pda}
+\showUnit{pdaakzeptanz}
+\showUnit{pdabeispiel}
 \end{document}