Mercurial > 13ss.theoinf
diff notes/tex/grammars.tex @ 41:5d10471f5585
move frame-definitions out of presentations
author | Markus Kaiser <markus.kaiser@in.tum.de> |
---|---|
date | Thu, 11 Jul 2013 20:42:36 +0200 |
parents | |
children | c14b92bfa07f |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/notes/tex/grammars.tex Thu Jul 11 20:42:36 2013 +0200 @@ -0,0 +1,310 @@ +\defineUnit{grammatik}{% +\begin{frame} + \frametitle{Grammatiken} + \setbeamercovered{dynamic} + + \begin{definition}[Kontextfreie Grammatik] + Eine \alert{kontextfreie Grammatik} $G = (V, \Sigma, P, S)$ ist ein 4-Tupel: + \begin{description} + \item[V] endlich viele \alert{Nichtterminale} (Variablen) + \item[$\Sigma$] ein Alphabet von \alert{Terminalen} + \item[P] endlich viele \alert{Produktionen} $\subseteq V \times \left( V \cup \Sigma \right)^*$ + \item[S] ein \alert{Startsymbol} + \end{description} + \end{definition} + + \begin{example}[Vorbereitung 3] + $\Sigma = \left\{ 0, 1 \right\}$. Grammatik für alle Wörter ungerader Länge, bei denen alle Nullen vor der ersten Eins stehen und weniger Nullen als Einsen vorhanden sind. + \pause + \[ + S \rightarrow 0S1 \mid S11 \mid 1 + \] + \end{example} +\end{frame} +} + +\defineUnit{ableitung}{% +\begin{frame} + \frametitle{Ableitungsrelation} + \setbeamercovered{dynamic} + + \begin{definition}[Ableitungsrelation] + Eine CFG $G$ induziert eine \alert{Ableitungsrelation} $\rightarrow_G$ auf Wörtern über $V \cup \Sigma$: + \[ + \alpha \rightarrow_G \beta + \] + gdw es eine Regel $A \rightarrow \gamma$ in $P$ mit Wörtern $\alpha_1, \alpha_2$ gibt, so dass + \[ + \alpha = \alpha_1\alert{A}\alpha_2 \quad \text{und} \quad \beta = \alpha_1 \alert{\gamma} \alpha_2 + \] + \end{definition} + + \begin{example}[Vorbereitung 3] + Mit den Produktionen $S \rightarrow 0S1 \mid S11 \mid 1$: + \begin{align*} + S &\rightarrow_G 0S1 \rightarrow_G 00S11 \rightarrow_G 00S1111 \rightarrow_G 0011111 \\ + \Rightarrow S &\rightarrow_G^* 0011111 + \end{align*} + \end{example} +\end{frame} +} + +\defineUnit{cfl}{% +\begin{frame}[c] + \frametitle{Kontextfreie Sprache} + \setbeamercovered{dynamic} + + \begin{definition}[Kontextfreie Sprache] + Eine kontextfreie Grammatik $G = (V, \Sigma, P, S)$ \alert{erzeugt} die Sprache + \[ + L(G) := \left\{ w \in \Sigma^* \mid S \rightarrow_G^* w \right\} + \] + Eine Sprache $L \subseteq \Sigma^*$ heißt \alert{kontextfrei} gdw es eine kontextfreie Grammatik $G$ gibt mit $L = L(G)$. + \end{definition} +\end{frame} +} + +\defineUnit{cnf}{% +\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} +} + +\defineUnit{cnfkonstruktion}{% +\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} +} + +\defineUnit{nuetzlichessymbol}{% +\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} +} + +\defineUnit{cyk}{% +\begin{frame} + \frametitle{CYK} + \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)$. \\ + 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}} \] + \end{definition} + + \begin{align*} + V_{ii} &= \left\{ A \in V \mid (A \rightarrow a_i) \in P \right\} \\ + V_{ij} &= \left\{ A \in V \mid \exists k, B \in V_{ik}, C \in V_{k+1,j} \;.\; (A \rightarrow BC) \in P \right\} + \end{align*} +\end{frame} +} + +\defineUnit{cykbeispiel}{% +\begin{frame} + \frametitle{CYK} + \setbeamercovered{dynamic} + + \begin{block}{Idee} + Kombiniere \alert{Teilwörter} zum ganzen Wort, wenn möglich. + \begin{enumerate} + \item Initialisiere mit den \alert{$V_{ii}$}. + \item<3-5> Befülle die Tabelle von unten nach oben. + \end{enumerate} + \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 \] + \begin{center} + \extrarowsep=5pt + \begin{tabu}to .8\textwidth{r|X[c]|X[c]|X[c]|X[c]|} + \tabucline{2-2} + 4 & \alt<-4>{}{$S,\ldots$} \\ \tabucline{2-3} + 3 & \alt<-3>{}{$\emptyset$} & \alt<-3>{}{$S, A, C$} \\ \tabucline{2-4} + 2 & \alt<-2>{}{$A$} & \alt<-2>{}{$B$} & \alt<-2>{}{$B$} \\ \tabucline{2-5} + 1 & \alt<-1>{}{$B$} & \alt<1>{}{$A,C$} & \alt<1>{}{$A,C$} & \alt<1>{}{$A,C$} \\ \tabucline{2-5} + \multicolumn{1}{r}{} & \multicolumn{1}{c}{\alert{b}} & \multicolumn{1}{c}{\alert{a}} & \multicolumn{1}{c}{\alert{a}} & \multicolumn{1}{c}{\alert{a}} \\ + \end{tabu} + \end{center} +\end{frame} +} + +\defineUnit{pda}{% +\begin{frame} + \frametitle{Kellerautomaten} + \setbeamercovered{dynamic} + + \begin{definition}[Kellerautomat] + Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem + \begin{itemize} + \item endlichen Menge von \alert{Zuständen} $Q$ + \item endlichen \alert{Eingabealphabet} $\Sigma$ + \item endlichen \alert{Kelleralphabet} $\Gamma$ + \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$ + \item \alert{Startzustand} $q_0 \in Q$ + \item \alert{Kellerinitialisierung} $Z_0 \in \Gamma$ + \item Menge von \alert{Endzuständen} $F \subseteq Q$ + \end{itemize} + \end{definition} + + \begin{center} + \begin{tikzpicture}[automaton, node distance=4cm] + \node[state] (q0) {$q_i$}; + \node[state] (q1) [right of = q0] {$q_j$}; + + \draw[every edge] (q0) edge node {$a, X/\gamma$} (q1); + \end{tikzpicture} + \end{center} +\end{frame} +} + +\defineUnit{pdaakzeptanz}{% +\begin{frame} + \frametitle{Kellerautomaten} + \setbeamercovered{dynamic} + + \begin{definition}[Kellerautomat] + Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem + \begin{itemize} + \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$ + \end{itemize} + \end{definition} + + \vfill + + \begin{definition}[Akzeptanz] + Ein PDA $P$ akzeptiert $w \in \Sigma^*$ \alert{mit Endzustand} gdw + \[ \exists \alert{f \in F}, \gamma \in \Gamma^*.(q_0, w, Z_0) \rightarrow_P^* (\alert{f}, \epsilon, \gamma) \] + Ein PDA $P$ akzeptiert $w \in \Sigma^*$ \alert{mit leerem Keller} gdw + \[ \exists q \in Q.(q_0, w, Z_0) \rightarrow_P^* (q, \epsilon, \alert{\epsilon}) \] + \end{definition} +\end{frame} +} + +\defineUnit{pdabeispiel}{% +\begin{frame} + \frametitle{Kellerautomaten} + \setbeamercovered{dynamic} + + \begin{definition}[Kellerautomat] + Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem + \begin{itemize} + + \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$ + \end{itemize} + \end{definition} + + \vfill + + \begin{example}[] + PDA akzeptierend \alert{mit leerem Keller} zu $L = \left\{ a^nb^n \mid n \in \N \right\}$. + + \centering + \begin{tikzpicture}[automaton] + + \node[state, initial] (q0) {$q_0$}; + \node[state] (q1) [right of = q0] {$q_1$}; + + \draw[->] (q0) edge [bend left] node {$\epsilon, A/A$} (q1); + \draw[->] (q0) edge [bend right] node [below] {$\epsilon, Z_0/Z_0$} (q1); + + \draw[->] (q0) edge [loop above] node {$a, Z_0/AZ_0$} (q0); + \draw[->] (q0) edge [loop below] node {$a, A/AA$} (q0); + + \draw[->] (q1) edge [loop above] node {$b, A/\epsilon$} (q1); + \draw[->] (q1) edge [loop below] node {$\epsilon, Z_0/\epsilon$} (q1); + \end{tikzpicture} + \end{example} +\end{frame} +}