# HG changeset patch # User Markus Kaiser # Date 1400253243 -7200 # Node ID 6a3cdddedcf7fbde2fa9c9776aaba348807e17c6 # Parent 02e25244ae1f54d9d677e20842298fbd1e75012b fifth sheet and notes diff -r 02e25244ae1f -r 6a3cdddedcf7 notes/tex/grammars.tex --- a/notes/tex/grammars.tex Wed May 14 21:58:31 2014 +0200 +++ b/notes/tex/grammars.tex Fri May 16 17:14:03 2014 +0200 @@ -424,9 +424,141 @@ \defineUnit{greibach}{% \begin{frame} - \frametitle{Greibach Normalform} + \frametitle{Greibach-Normalform} + + \begin{definition}[Greibach-Normalform] + Eine kontextfreie Grammatik ist in \structure{Greibach-Normalform} (GNF) genau dann wenn alle Produktionen außer $S \to \epsilon$ die Form + \[ + A \rightarrow \alert{a\alpha} \quad \text{mit} \quad a \in \Sigma, \alpha \in V^* + \] + haben. + \end{definition} + + \vfill + + \begin{theorem} + Zu \alert{jeder} CFG $G$ existiert eine CFG $G'$ in Greibach-Normalform mit + \[ + L(G') = L(G) + \] + \end{theorem} +\end{frame} + +\begin{frame} + \frametitle{Einsetzen von Produktionen} + + \begin{theorem}[Einsetzen von Produktionen] + Enthält eine CFG die Produktionen + \begin{align} + A &\to \alpha_1 \structure{B} \alpha_2\\ + \structure{B} &\to \alert{\beta_1} \mid \dots \mid \alert{\beta_k} + \intertext{so ändert sich die erzeugte Sprache nicht, wenn man $B$ in $A$ \structure{einsetzt}.} + A &\to \alpha_1 \alert{\beta_1} \alpha_2 \mid \dots \mid \alpha_1 \alert{\beta_k} \alpha_2 + \end{align} + \end{theorem} + + \vfill + + \begin{example} + Die Grammatik + \begin{align} + S &\to a \mid a\structure{B}c \\ + \structure{B} &\to \alert{b} \mid \alert{bS} + \intertext{ist äquivalent zur Grammatik} + S &\to a \mid a\alert{b}c \mid a\alert{bS}c + \end{align} + \end{example} +\end{frame} + +\begin{frame} + \frametitle{Linksrekursive Produktionen} + + \begin{definition}[Linksrekursive Produktion] + Man nennt eine Produktion \structure{linksrekursiv}, wenn sie die Form + \[ + \structure{A} \to \structure{A}\alpha_1 \mid \dots \mid \structure{A}\alpha_k \mid \beta_i \mid \dots \mid \beta_l \quad \text{mit} \quad \alpha_i, \beta_i \in \left( V \cup \Sigma \right)^+ + \] + hat, wobei die $\beta_i$ nicht mit $A$ beginnen. + \end{definition} + + \vfill - Stuff. + \begin{theorem}[Ersetzen von linksrekursiven Produktionen] + Sei $A$ eine linksrekursive Produktion einer CFG.\\ + Dann ändert sich die erzeugte Sprache nicht, wenn wir $A$ \structure{ersetzen} durch + \begin{align} + \structure{A} &\to \beta_1 \mid \dots \mid \beta_l \mid \beta_1 \alert{B} \mid \dots \mid \beta_l \alert{B}\\ + \alert{B} &\to \alpha_1 \mid \dots \mid \alpha_k \mid \alpha_1 \alert{B} \mid \dots \mid \alpha_k \alert{B} + \end{align} + \alert{$B$} ist niemals linksrekursiv. + \end{theorem} +\end{frame} +} + +\defineUnit{greibachkonstruktion}{% +\begin{frame} + \frametitle{GNF Konstruktion} + + \begin{block}{GNF Konstruktion} + Sei $G = (V, \Sigma, P, S)$ eine CFG. + \begin{enumerate} + \item<1,2-> \alert{Nummeriere} Nichtterminale + \item<1,3-> Mache Prduktionen \alert{aufsteigend} und \alert{nicht rekursiv} + \item<1,5-> \alert{Setze} Produktionen absteigend \alert{ein} + \end{enumerate} + \end{block} + + \vspace{1em} + + \only<2> { + Benenne alle Nichtterminale \structure{beliebig} um in $A_1, \dots, A_\abs{V}$. + \begin{align} + S &\rightarrow Ab, \quad A \rightarrow aAS \mid \epsilon \\ + \intertext{wird zu} + A_1 &\to A_2b\\ + A_2 &\to aA_2A_1 + \end{align} + } + + \only<3,4> { + Betrachte alle Produktionen $A_l \to \dots$ in \structure{aufsteigender Reihenfolge}.\\ + \begin{itemize} + \item Existieren Produktionen der Form $A_l \to \structure{A_r}\alpha$ mit \alert{$r < l$}, dann setze \structure{$A_r$} in $A_l$ ein. + \only<3> { + \begin{align} + A_1 &\to A_2 \mid a \mid b \\ + A_2 &\to \structure{A_1}xA_1 + \intertext{wird zu} + A_1 &\to a \mid b\\ + A_2 &\to \structure{A_2}xA_1 \mid \structure{a}xA_1 \mid \structure{b}xA_1 + \end{align} + } + \item Entferne danach alle \structure{linksrekursiven} $A_l$-Produktionen. + \only<4> { + \begin{align} + A_2 &\to A_2\structure{xA_1} \mid \alert{axA_1} \mid \alert{bxA_1} + \intertext{wird zu} + A_2 &\to \alert{axA_1} \mid \alert{bxA_1} \mid \alert{axA_1}A_3 \mid \alert{bxA_1}A_3\\ + A_3 &\to \structure{xA_1} \mid \structure{xA_1}A_3 + \end{align} + } + \end{itemize} + } + + \only<5> { + Betrachte alle Produktionen $A_l \to \dots$ in \structure{absteigender Reihenfolge}.\\ + \begin{itemize} + \item Existieren Produktionen der Form $A_l \to \structure{A_r}\alpha$ mit \alert{$r > l$}, dann setze \structure{$A_r$} in $A_l$ ein. + \begin{align} + A_1 &\to a \mid b \mid \structure{A_2} \\ + A_2 &\to axA_1 \mid bxA_1 \mid axA_1A_3 \mid bxA_1A_3\\ + A_3 &\to xA_1 \mid xA_1A_3 + \intertext{$A_1$ wird zu} + A_1 &\to a \mid b \mid \structure{axA_1} \mid \structure{bxA_1} \mid \structure{axA_1A_3} \mid \structure{bxA_1A_3} + \end{align} + \end{itemize} + + } \end{frame} } @@ -510,7 +642,7 @@ \node[state] (q1) [right of = q0] {$q_1$}; \node[state] (q2) [right of = q1] {$q_2$}; - \draw[->] (q0) edge [loop above] node {$\epsilon, Z_0/\epsilon$}; + \draw[->] (q0) edge [loop above] node {$\epsilon, Z_0/\epsilon$} (q0); \draw[->] (q0) edge node {$a, Z_0/AZ_0$} (q1); \draw[->] (q1) edge node {$\epsilon, A/A$} (q2); diff -r 02e25244ae1f -r 6a3cdddedcf7 notes/tex/ue05_notes.tex --- a/notes/tex/ue05_notes.tex Wed May 14 21:58:31 2014 +0200 +++ b/notes/tex/ue05_notes.tex Fri May 16 17:14:03 2014 +0200 @@ -10,6 +10,7 @@ \showUnit{induktivesprachdefinition} \showUnit{ogden} \showUnit{greibach} +\showUnit{greibachkonstruktion} \showUnit{pda} \showUnit{pdaakzeptanz} \showUnit{pdabeispiel} diff -r 02e25244ae1f -r 6a3cdddedcf7 notes/ue05_notes.pdf Binary file notes/ue05_notes.pdf has changed diff -r 02e25244ae1f -r 6a3cdddedcf7 ue05.pdf Binary file ue05.pdf has changed