# HG changeset patch
# User Markus Kaiser <markus.kaiser@in.tum.de>
# Date 1399743541 -7200
# Node ID a08f6e33cfb04bfdd84e1f64544242dca26e3f37
# Parent  60757c0ba1f0e4891573d0e2da024558ac66d837
fourth sheet and notes

diff -r 60757c0ba1f0 -r a08f6e33cfb0 notes/tex/automata.tex
--- a/notes/tex/automata.tex	Fri May 09 11:28:33 2014 +0200
+++ b/notes/tex/automata.tex	Sat May 10 19:39:01 2014 +0200
@@ -489,11 +489,12 @@
 
 \defineUnit{rpl}{%
 \begin{frame}
-    \frametitle{Pumping Lemma}
+    \frametitle{Pumping Lemma für reguläre Sprachen}
     \setbeamercovered{dynamic}
 
     \begin{theorem}[Pumping Lemma für reguläre Sprachen]
-        Sei $R \subseteq \Sigma^*$ regulär. Dann gibt es ein $n > 0$, so dass sich \alert{jedes} $z \in R$ mit $|z| \geq n$ so in $z = uvw$ zerlegen lässt, dass
+        Sei $R \subseteq \Sigma^*$ regulär.\\
+        Dann gibt es ein $n > 0$, so dass sich \alert{jedes} $z \in R$ mit $|z| \geq n$ so in $z = uvw$ zerlegen lässt, dass
         \begin{itemize}
             \item $v \neq \epsilon$
             \item $|uv| \alert{\leq n}$
@@ -504,14 +505,20 @@
     \vfill
 
     \begin{center}
-        \begin{tikzpicture}[automaton]
-            \node[state, initial] (q0) {};
-            \node[state, fill=tumred!20] (q1) [right of=q0] {};
-            \node[state, accepting] (q2) [right of=q1] {};
+        \begin{tikzpicture}[automaton, node distance=2.5cm]
+            \node[state, initial] (qi) {};
+            \node[state, fill=tumred!20] (q0) [right = 3 of qi] {};
+            \node[state, fill=tumred!20] (q1) [above left of=q0] {};
+            \node[state, fill=tumred!20] (q2) [above right of=q0] {};
+            \node[state, accepting] (qf) [right = 3 of q0] {};
 
-            \draw[->, densely dashed] (q0) edge node {$u$} (q1);
-            \draw[->, tumred] (q1) edge [loop above] node {$v$} (q1);
-            \draw[->, densely dashed] (q1) edge node {$w$} (q2);
+            \draw[->, densely dashed] (qi) edge node {$u$} (q0);
+            \draw[tumred, densely dashed]
+                (q0) edge (q1)
+                (q1) edge (q2)
+                (q2) edge (q0);
+            \node[tumred] at (barycentric cs:q0=1,q1=1,q2=1) {$v$};
+            \draw[->, densely dashed] (q0) edge node {$w$} (qf);
         \end{tikzpicture}
     \end{center}
 \end{frame}
diff -r 60757c0ba1f0 -r a08f6e33cfb0 notes/tex/grammars.tex
--- a/notes/tex/grammars.tex	Fri May 09 11:28:33 2014 +0200
+++ b/notes/tex/grammars.tex	Sat May 10 19:39:01 2014 +0200
@@ -160,7 +160,7 @@
     \setbeamercovered{dynamic}
 
     \begin{definition}[Chomsky-Normalform]
-        Eine kontextfreie Grammatik ist in \alert{Chomsky-Normalform} (CNF) genau dann wenn alle Produktionen die Form
+        Eine kontextfreie Grammatik ist in \structure{Chomsky-Normalform} (CNF) genau dann wenn alle Produktionen die Form
         \[
             A \rightarrow \alert{a} \quad \text{oder} \quad A \rightarrow \alert{BC}
         \]
@@ -183,7 +183,7 @@
     \frametitle{CNF Konstruktion}
     \setbeamercovered{dynamic}
 
-    \begin{block}{Idee}
+    \begin{block}{CNF Konstruktion}
         Sei $G = (V, \Sigma, P, S)$ eine CFG.
         \begin{enumerate}
             \item<1,2-> Eliminiere \alert{$\epsilon$-Produktionen}
@@ -269,7 +269,8 @@
     \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
+        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}$
@@ -339,7 +340,7 @@
     \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)$. \\
+        Der \structure{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}} \]
@@ -357,7 +358,7 @@
     \frametitle{CYK}
     \setbeamercovered{dynamic}
 
-    \begin{block}{Idee}
+    \begin{block}{CYK-Algorithmus}
         Kombiniere \alert{Teilwörter} zum ganzen Wort, wenn möglich.
         \begin{enumerate}
             \item Initialisiere mit den \alert{$V_{ii}$}.
@@ -366,6 +367,7 @@
     \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 \]
+    \vspace{2em}
     \begin{center}
         \extrarowsep=5pt
         \begin{tabu}to .8\textwidth{r|X[c]|X[c]|X[c]|X[c]|}
diff -r 60757c0ba1f0 -r a08f6e33cfb0 notes/tex/ue04_notes.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/ue04_notes.tex	Sat May 10 19:39:01 2014 +0200
@@ -0,0 +1,17 @@
+\input{preamble.tex}
+\input{frames.tex}
+
+\title{Übung 4: Pumping-Lemmata, CNF und CYK}
+\subtitle{Theoretische Informatik Sommersemester 2014}
+\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
+
+\begin{document}
+\showUnit{titel}
+\showUnit{rpl}
+\showUnit{nuetzlichessymbol}
+\showUnit{cnf}
+\showUnit{cfpl}
+\showUnit{cnfkonstruktion}
+\showUnit{cyk}
+\showUnit{cykbeispiel}
+\end{document}
diff -r 60757c0ba1f0 -r a08f6e33cfb0 notes/ue04_notes.pdf
Binary file notes/ue04_notes.pdf has changed
diff -r 60757c0ba1f0 -r a08f6e33cfb0 ue04.pdf
Binary file ue04.pdf has changed