next up previous
Next: Exercise 3. Up: Quiz5 Previous: Exercise 1.

Exercise 2.

We consider the alphabet $ \Sigma$ = {a, b} and the grammar G below. Let L be the language generated by G over $ \Sigma$.

G $\displaystyle \left\{\vphantom{ \begin{array}{rcl} S & \longmapsto & AB \\  A &...
...longmapsto & b B B \\  B & \longmapsto & {\varepsilon} \\  \end{array} }\right.$$\displaystyle \begin{array}{rcl} S & \longmapsto & AB \\  A & \longmapsto & a A...
...\\  B & \longmapsto & b B B \\  B & \longmapsto & {\varepsilon} \\  \end{array}$
   

Give a grammar G' generating L $ \setminus$ {$ \varepsilon$} and with no $ \varepsilon$-productions, that is no rules of the form X $ \longmapsto$ $ \varepsilon$, where $ \varepsilon$ denotes the empty word. Is G' left-recursive?

Answer 2  
\fbox{
\begin{minipage}{13 cm}
\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\mbox{ } \...
...\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\end{minipage}}


next up previous
Next: Exercise 3. Up: Quiz5 Previous: Exercise 1.
Marc Moreno Maza
2004-12-02