Mercurial > 14ss.theoinf
comparison 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 |
comparison
equal
deleted
inserted
replaced
| 15:60757c0ba1f0 | 16:a08f6e33cfb0 |
|---|---|
| 158 \begin{frame} | 158 \begin{frame} |
| 159 \frametitle{CNF} | 159 \frametitle{CNF} |
| 160 \setbeamercovered{dynamic} | 160 \setbeamercovered{dynamic} |
| 161 | 161 |
| 162 \begin{definition}[Chomsky-Normalform] | 162 \begin{definition}[Chomsky-Normalform] |
| 163 Eine kontextfreie Grammatik ist in \alert{Chomsky-Normalform} (CNF) genau dann wenn alle Produktionen die Form | 163 Eine kontextfreie Grammatik ist in \structure{Chomsky-Normalform} (CNF) genau dann wenn alle Produktionen die Form |
| 164 \[ | 164 \[ |
| 165 A \rightarrow \alert{a} \quad \text{oder} \quad A \rightarrow \alert{BC} | 165 A \rightarrow \alert{a} \quad \text{oder} \quad A \rightarrow \alert{BC} |
| 166 \] | 166 \] |
| 167 haben. | 167 haben. |
| 168 \end{definition} | 168 \end{definition} |
| 181 \defineUnit{cnfkonstruktion}{% | 181 \defineUnit{cnfkonstruktion}{% |
| 182 \begin{frame} | 182 \begin{frame} |
| 183 \frametitle{CNF Konstruktion} | 183 \frametitle{CNF Konstruktion} |
| 184 \setbeamercovered{dynamic} | 184 \setbeamercovered{dynamic} |
| 185 | 185 |
| 186 \begin{block}{Idee} | 186 \begin{block}{CNF Konstruktion} |
| 187 Sei $G = (V, \Sigma, P, S)$ eine CFG. | 187 Sei $G = (V, \Sigma, P, S)$ eine CFG. |
| 188 \begin{enumerate} | 188 \begin{enumerate} |
| 189 \item<1,2-> Eliminiere \alert{$\epsilon$-Produktionen} | 189 \item<1,2-> Eliminiere \alert{$\epsilon$-Produktionen} |
| 190 \item<1,3-> Eliminiere \alert{Kettenproduktionen} | 190 \item<1,3-> Eliminiere \alert{Kettenproduktionen} |
| 191 \item<1,4-> \alert{Ersetze Terminale} durch Nichtterminale | 191 \item<1,4-> \alert{Ersetze Terminale} durch Nichtterminale |
| 267 \begin{frame} | 267 \begin{frame} |
| 268 \frametitle{Pumping Lemma für CFLs} | 268 \frametitle{Pumping Lemma für CFLs} |
| 269 \setbeamercovered{dynamic} | 269 \setbeamercovered{dynamic} |
| 270 | 270 |
| 271 \begin{theorem}[Pumping Lemma für kontextfreie Sprachen] | 271 \begin{theorem}[Pumping Lemma für kontextfreie Sprachen] |
| 272 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 | 272 Sei $L \subseteq \Sigma^*$ kontextfrei.\\ |
| 273 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 | |
| 273 \begin{itemize} | 274 \begin{itemize} |
| 274 \item $vx \alert{\neq \epsilon}$ | 275 \item $vx \alert{\neq \epsilon}$ |
| 275 \item $|vwx| \alert{\leq n}$ | 276 \item $|vwx| \alert{\leq n}$ |
| 276 \item $\forall i \alert{\geq 0}. uv^iwx^iy \in L$ | 277 \item $\forall i \alert{\geq 0}. uv^iwx^iy \in L$ |
| 277 \end{itemize} | 278 \end{itemize} |
| 337 \begin{frame} | 338 \begin{frame} |
| 338 \frametitle{CYK} | 339 \frametitle{CYK} |
| 339 \setbeamercovered{dynamic} | 340 \setbeamercovered{dynamic} |
| 340 | 341 |
| 341 \begin{definition}[Cocke-Younger-Kasami-Algorithmus] | 342 \begin{definition}[Cocke-Younger-Kasami-Algorithmus] |
| 342 Der \alert{CYK-Algorithmus} entscheidet das Wortproblem für kontextfreie Grammatiken in Chomsky-Normalform in $\Oh(n^3)$. \\ | 343 Der \structure{CYK-Algorithmus} entscheidet das Wortproblem für kontextfreie Grammatiken in Chomsky-Normalform in $\Oh(n^3)$. \\ |
| 343 Gegeben eine \alert{Grammatik} $G = (V, \Sigma, P, S)$ in CNF und ein \alert{Wort} $w = a_1 \ldots a_n \in \Sigma^*$. | 344 Gegeben eine \alert{Grammatik} $G = (V, \Sigma, P, S)$ in CNF und ein \alert{Wort} $w = a_1 \ldots a_n \in \Sigma^*$. |
| 344 Mit \[ V_{ij} := \left\{ A \in V \mid A \rightarrow_G^* \alert{a_i \ldots a_j} \right\}\] | 345 Mit \[ V_{ij} := \left\{ A \in V \mid A \rightarrow_G^* \alert{a_i \ldots a_j} \right\}\] |
| 345 ist \[ w \in L(G) \Leftrightarrow S \in V_{\alert{1n}} \] | 346 ist \[ w \in L(G) \Leftrightarrow S \in V_{\alert{1n}} \] |
| 346 \end{definition} | 347 \end{definition} |
| 347 | 348 |
| 355 \defineUnit{cykbeispiel}{% | 356 \defineUnit{cykbeispiel}{% |
| 356 \begin{frame} | 357 \begin{frame} |
| 357 \frametitle{CYK} | 358 \frametitle{CYK} |
| 358 \setbeamercovered{dynamic} | 359 \setbeamercovered{dynamic} |
| 359 | 360 |
| 360 \begin{block}{Idee} | 361 \begin{block}{CYK-Algorithmus} |
| 361 Kombiniere \alert{Teilwörter} zum ganzen Wort, wenn möglich. | 362 Kombiniere \alert{Teilwörter} zum ganzen Wort, wenn möglich. |
| 362 \begin{enumerate} | 363 \begin{enumerate} |
| 363 \item Initialisiere mit den \alert{$V_{ii}$}. | 364 \item Initialisiere mit den \alert{$V_{ii}$}. |
| 364 \item<3-5> Befülle die Tabelle von unten nach oben. | 365 \item<3-5> Befülle die Tabelle von unten nach oben. |
| 365 \end{enumerate} | 366 \end{enumerate} |
| 366 \end{block} | 367 \end{block} |
| 367 | 368 |
| 368 \[ S \rightarrow AB \mid BC, \quad A \rightarrow BA \mid a, \quad B \rightarrow CC \mid b, \quad C \rightarrow AB \mid a \] | 369 \[ S \rightarrow AB \mid BC, \quad A \rightarrow BA \mid a, \quad B \rightarrow CC \mid b, \quad C \rightarrow AB \mid a \] |
| 370 \vspace{2em} | |
| 369 \begin{center} | 371 \begin{center} |
| 370 \extrarowsep=5pt | 372 \extrarowsep=5pt |
| 371 \begin{tabu}to .8\textwidth{r|X[c]|X[c]|X[c]|X[c]|} | 373 \begin{tabu}to .8\textwidth{r|X[c]|X[c]|X[c]|X[c]|} |
| 372 \tabucline{2-2} | 374 \tabucline{2-2} |
| 373 4 & \alt<-4>{}{$S,\ldots$} \\ \tabucline{2-3} | 375 4 & \alt<-4>{}{$S,\ldots$} \\ \tabucline{2-3} |