diff notes/tex/grammars.tex @ 16:a08f6e33cfb0

fourth sheet and notes
author Markus Kaiser <markus.kaiser@in.tum.de>
date Sat, 10 May 2014 19:39:01 +0200
parents de844d67518b
children 0f7daeda8363
line wrap: on
line diff
--- 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]|}