14ss.theoinf: notes/tex/grammars.tex comparison

comparison notes/tex/grammars.tex @ 21:6a3cdddedcf7

fifth sheet and notes

author	Markus Kaiser <markus.kaiser@in.tum.de>
date	Fri, 16 May 2014 17:14:03 +0200
parents	02e25244ae1f
children	334369297f54

comparison

equal deleted inserted replaced

-:02e25244ae1f
+:6a3cdddedcf7
 \end{frame}
 }
 \defineUnit{greibach}{%
 \begin{frame}
-\frametitle{Greibach Normalform}
+\frametitle{Greibach-Normalform}
-Stuff.
+\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
+\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}
 }
 \defineUnit{pda}{%
 \begin{frame}
 \node[state, initial] (q0) {$q_0$};
 \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);
 \draw[->] (q1) edge [loop above] node {$a, */A*$} (q1);

Mercurial > 14ss.theoinf

comparison notes/tex/grammars.tex @ 21:6a3cdddedcf7