Mercurial > 13ss.theoinf
diff notes/tex/ue06_notes.tex @ 44:15351d87ce76
transition notes
author | Markus Kaiser <markus.kaiser@in.tum.de> |
---|---|
date | Thu, 11 Jul 2013 22:06:26 +0200 |
parents | 90ffda7e20c7 |
children |
line wrap: on
line diff
--- a/notes/tex/ue06_notes.tex Thu Jul 11 21:57:50 2013 +0200 +++ b/notes/tex/ue06_notes.tex Thu Jul 11 22:06:26 2013 +0200 @@ -1,184 +1,14 @@ \input{preamble.tex} +\input{frames.tex} \title{Übung 6: CNF und CFL-Pumping Lemma} \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{CNF} - \setbeamercovered{dynamic} - - \begin{definition}[Chomsky-Normalform] - Eine kontextfreie Grammatik ist in \alert{Chomsky-Normalform} (CNF) genau dann wenn alle Produktionen die Form - \[ - A \rightarrow \alert{a} \quad \text{oder} \quad A \rightarrow \alert{BC} - \] - haben. - \end{definition} - - \vfill - - \begin{theorem} - Zu \alert{jeder} CFG $G$ existiert eine CFG $G'$ in Chomsky-Normalform mit - \[ - L(G') = L(G) \alert{\setminus \left\{ \epsilon \right\}} - \] - \end{theorem} -\end{frame} - -\begin{frame} - \frametitle{CNF Konstruktion} - \setbeamercovered{dynamic} - - \begin{block}{Idee} - Sei $G = (V, \Sigma, P, S)$ eine CFG. - \begin{enumerate} - \item<1,2-> Eliminiere \alert{$\epsilon$-Produktionen} - \item<1,3-> Eliminiere \alert{Kettenproduktionen} - \item<1,4-> \alert{Ersetze Terminale} durch Nichtterminale - \item<1,5-> \alert{Verkürze Ketten} von Nichtterminalen der Länge $\geq 3$ - \end{enumerate} - \end{block} - - \vspace{1em} - - \only<2> { - Sind \alert{$B \rightarrow \epsilon$} und \alert{$A \rightarrow \alpha B \beta$} in $P$, dann füge \alert{$A \rightarrow \alpha \beta$} hinzu. Entferne danach alle $\epsilon$-Produktionen. - \begin{align*} - S &\rightarrow Ab, \quad A \rightarrow aAA \mid \epsilon \\ - \intertext{neu:} - S &\rightarrow \alert{b} \\ - A &\rightarrow \alert{aA \mid a} - \end{align*} - } - - \only<3> { - Sind \alert{$A \rightarrow B$} und \alert{$B \rightarrow \alpha$} in $P$, dann füge \alert{$A \rightarrow \alpha$} hinzu. Entferne danach alle Kettenproduktionen und unerreichbaren Symbole. - \begin{align*} - S &\rightarrow A, \quad A \rightarrow a \mid B, \quad B \rightarrow bS \\ - \intertext{neu:} - A &\rightarrow \alert{a \mid bS} \\ - S &\rightarrow \alert{a \mid bS} - \end{align*} - } - - \only<4> { - Ersetze jedes \alert{$a \in \Sigma$} in einer rechten Seite \alert{länger als $1$} durch ein neues Nichtterminal. - \begin{align*} - S &\rightarrow aa \mid Bb \mid b, \quad B \rightarrow \ldots \\ - \intertext{neu:} - S &\rightarrow \alert{X_aX_a \mid BX_b \mid b} \\ - X_a &\rightarrow \alert{a}, \quad X_b \rightarrow \alert{b} - \end{align*} - } - - \only<5> { - Ersetze jede Produktion der Form $A \rightarrow B_1B_2\ldots B_k$ durch neue Nichtterminale mit Produktionen der Länge $2$. - \begin{align*} - S &\rightarrow X_aX_bBX_a, \quad X_a \rightarrow a, \quad X_b \rightarrow b, \quad B \rightarrow \ldots \\ - \intertext{neu:} - S &\rightarrow \alert{X_aT_1} \\ - T_1 &\rightarrow \alert{X_bT_2}, \quad T_2 \rightarrow \alert{BX_a} \\ - \end{align*} - } -\end{frame} - -\begin{frame} - \frametitle{Eigenschaften von Symbolen} - \setbeamercovered{dynamic} - - \begin{definition} - Sei $G = (V, \Sigma, P, S)$ eine CFG. \\ - Ein Symbol $X \in V \cup \Sigma$ ist - \begin{description} - \item[nützlich] es gibt $S \rightarrow_G^* w \in \Sigma^*$ in der X \alert{vorkommt} - \item[erzeugend] es gibt $\alert{X} \rightarrow_G^* w \in \Sigma^*$ - \item[erreichbar] es gibt $S \rightarrow_G^* \alpha \alert{X} \beta$ - \end{description} - \end{definition} - - \vfill - - \begin{theorem} - Nützliche Symbole \alert{sind} erzeugend und erreichbar. Aber \alert{nicht} notwendigerweise umgekehrt. - \[ - S \rightarrow AB \mid a, \quad A \rightarrow b - \] - \end{theorem} -\end{frame} - -\begin{frame} - \frametitle{Pumping Lemma für CFLs} - \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 - \begin{itemize} - \item $vx \alert{\neq \epsilon}$ - \item $|vwx| \alert{\leq n}$ - \item $\forall i \alert{\geq 0}. uv^iwx^iy \in L$ - \end{itemize} - \end{theorem} - - \vfill - - \begin{center} - \begin{columns} - \begin{column}{.4\textwidth} - \begin{tikzpicture} - \coordinate (outer) at (2, 2.4); - \coordinate (middle) at (2.2, 1.2); - \coordinate (inner) at (2.2, 0.6); - % outer - \draw[fill=tumred!40] (0, 0) -- (1.2, 0) -- (middle) -- (3.2, 0) -- (4, 0) -- (outer) node[above] {$S$} -- (0, 0); - % middle - \draw[fill=tumgreen!40] (1.2, 0) -- (1.7, 0) -- (inner) -- (2.7, 0) -- (3.2, 0) -- (middle) -- (1.2, 0); - % inner - \draw[fill=tumblue!40] (1.7, 0) -- (inner) -- (2.7, 0) -- (1.7, 0); - - % path - \draw[dashed, thick] (outer) -- (middle) -- (inner); - \draw[fill] (outer) circle (1pt); - \draw[fill] (middle) circle (1pt); - \draw[fill] (inner) circle (1pt); - - % nodes - \node[below] at (0.6, 0) {$u$}; - \node[below] at (1.45, 0) {$v$}; - \node[below] at (2.2, 0) {$w$}; - \node[below] at (2.95, 0) {$x$}; - \node[below] at (3.6, 0) {$y$}; - \end{tikzpicture} - \end{column} - \begin{column}{.4\textwidth} - \begin{tikzpicture} - \coordinate (outer) at (2, 2.4); - \coordinate (middle) at (2.2, 1.2); - \coordinate (inner) at (2.2, 0.6); - % outer - \draw[fill=tumred!40] (0, 0) -- (1.2, 0) -- (middle) -- (3.2, 0) -- (4, 0) -- (outer) node[above] {$S$} -- (0, 0); - % inner - \draw[fill=tumblue!40] (1.7, 0.6) -- (middle) -- (2.7, 0.6) -- (1.7, 0.6); - - % path - \draw[dashed, thick] (outer) -- (middle); - \draw[fill] (outer) circle (1pt); - \draw[fill] (middle) circle (1pt); - - % nodes - \node[below] at (0.6, 0) {$u$}; - \node[below] at (2.2, 0) {$w$}; - \node[below] at (3.6, 0) {$y$}; - \end{tikzpicture} - \end{column} - \end{columns} - \end{center} -\end{frame} - +\showUnit{titel} +\showUnit{cnf} +\showUnit{cnfkonstruktion} +\showUnit{nuetzlichessymbol} +\showUnit{cfpl} \end{document}