next up previous
Next: Exercise 4 Up: The Assignment Previous: Exercise 2

Exercise 3

We consider the grammar G with Let $ \Sigma$ be the alphabet consisting of the six terminals of G. Hence

$\displaystyle \Sigma$ = {( , ) , $\displaystyle \bf\mid$ , $\displaystyle \bf {}^{\ast}$ , $\displaystyle \bf a$ , $\displaystyle \bf b$}. (2)

Let L be the language over $ \Sigma$ generated by G.
  1. Is the language L regular?
  2. Show that the language L is context-free.
  3. Construct a parse tree for the expression $ \bf a$($ \bf a$ $ \bf\mid$$ \bf b$) $ \bf {}^{\ast}$.
  4. Show that G is ambiguous.


next up previous
Next: Exercise 4 Up: The Assignment Previous: Exercise 2
Marc Moreno Maza
2004-12-01