next up previous
Next: Exercise 4. Up: Final-2003 Previous: Exercise 2.

Exercise 3.

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}$
   

  1. 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.
  2. If L is regular then give a regular expression for L otherwise tell whether G' is anbiguous or not.

Answer 3  
\fbox{
\begin{minipage}{12 cm}
\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\mbox{ } \...
...\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\end{minipage}}


next up previous
Next: Exercise 4. Up: Final-2003 Previous: Exercise 2.
Marc Moreno Maza
2004-12-02