Exercise 3

We consider the grammar G with

• the six terminals ( , ) , $\bf\mid$ , $\bf {}^{\ast}$ , $\bf a$ and $\bf b$ (the opening parenthesis, the closing parenthesis, the pipe, the star, the lower-case letter a, the lower-case letter b)
• the non-terminal and start symbol R
• the six productions below

  R	$\longmapsto$	R $\bf\mid$ R
  R	$\longmapsto$	R R
  R	$\longmapsto$	R$\bf\ast$
  R	$\longmapsto$	(R)
  R	$\longmapsto$	$\bf a$
  R	$\longmapsto$	$\bf b$

Let $\Sigma$ be the alphabet consisting of the six terminals of G. Hence

$$\Sigma \bf\mid \bf {}^{\ast} \bf a \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.