Mercurial > 14ss.theoinf
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]|}