Mercurial > 13ss.theoinf

comparison notes/tex/grammars.tex @ 58:aac2480571b8 default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
rewrite ambiguous slide
author Markus Kaiser <markus.kaiser@in.tum.de>
date Tue, 30 Jul 2013 14:32:43 +0200
parents 72ac27051d7e
children
comparison
equal deleted inserted replaced
57:3ac958d9b7c4 58:aac2480571b8
134 134
135 \only<2> { 135 \only<2> {
136 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. 136 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.
137 \begin{align*} 137 \begin{align*}
138 S &\rightarrow Ab, \quad A \rightarrow aAA \mid \epsilon \\ 138 S &\rightarrow Ab, \quad A \rightarrow aAA \mid \epsilon \\
139 \intertext{neu:} 139 \intertext{wird zu:}
140 S &\rightarrow \alert{b} \\ 140 S &\rightarrow \alert{Ab \mid b} \\
141 A &\rightarrow \alert{aA \mid a} 141 A &\rightarrow \alert{aAA \mid aA \mid a}
142 \end{align*} 142 \end{align*}
143 } 143 }
144 144
145 \only<3> { 145 \only<3> {
146 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. 146 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.
147 \begin{align*} 147 \begin{align*}
148 S &\rightarrow A, \quad A \rightarrow a \mid B, \quad B \rightarrow bS \\ 148 S &\rightarrow A, \quad A \rightarrow a \mid B, \quad B \rightarrow bS \\
149 \intertext{neu:} 149 \intertext{wird zu:}
150 A &\rightarrow \alert{a \mid bS} \\ 150 A &\rightarrow \alert{a \mid bS} \\
151 S &\rightarrow \alert{a \mid bS} 151 S &\rightarrow \alert{a \mid bS}
152 \end{align*} 152 \end{align*}
153 } 153 }
154 154
155 \only<4> { 155 \only<4> {
156 Ersetze jedes \alert{$a \in \Sigma$} in einer rechten Seite \alert{länger als $1$} durch ein neues Nichtterminal. 156 Ersetze jedes \alert{$a \in \Sigma$} in einer rechten Seite \alert{länger als $1$} durch ein neues Nichtterminal.
157 \begin{align*} 157 \begin{align*}
158 S &\rightarrow aa \mid Bb \mid b, \quad B \rightarrow \ldots \\ 158 S &\rightarrow aa \mid Bb \mid b, \quad B \rightarrow \ldots \\
159 \intertext{neu:} 159 \intertext{wird zu:}
160 S &\rightarrow \alert{X_aX_a \mid BX_b \mid b} \\ 160 S &\rightarrow \alert{X_aX_a \mid BX_b \mid b} \\
161 X_a &\rightarrow \alert{a}, \quad X_b \rightarrow \alert{b} 161 X_a &\rightarrow \alert{a}, \quad X_b \rightarrow \alert{b}
162 \end{align*} 162 \end{align*}
163 } 163 }
164 164
165 \only<5> { 165 \only<5> {
166 Ersetze jede Produktion der Form $A \rightarrow B_1B_2\ldots B_k$ durch neue Nichtterminale mit Produktionen der Länge $2$. 166 Ersetze jede Produktion der Form $A \rightarrow B_1B_2\ldots B_k$ durch neue Nichtterminale mit Produktionen der Länge $2$.
167 \begin{align*} 167 \begin{align*}
168 S &\rightarrow X_aX_bBX_a, \quad X_a \rightarrow a, \quad X_b \rightarrow b, \quad B \rightarrow \ldots \\ 168 S &\rightarrow X_aX_bBX_a, \quad X_a \rightarrow a, \quad X_b \rightarrow b, \quad B \rightarrow \ldots \\
169 \intertext{neu:} 169 \intertext{wird zu:}
170 S &\rightarrow \alert{X_aT_1} \\ 170 S &\rightarrow \alert{X_aT_1} \\
171 T_1 &\rightarrow \alert{X_bT_2}, \quad T_2 \rightarrow \alert{BX_a} \\ 171 T_1 &\rightarrow \alert{X_bT_2}, \quad T_2 \rightarrow \alert{BX_a} \\
172 \end{align*} 172 \end{align*}
173 } 173 }
174 \end{frame} 174 \end{frame}