Exercise 1

We consider the grammar G with

• the four terminals ( , ) , , and $\bf a$ (the opening parenthesis, the closing parenthesis, the comma and the lower-case letter a)
• the three non-terminals S, L, E
• the start symbol S
• the six productions below

  S	$\longmapsto$	$\bf a$
  S	$\longmapsto$	L
  L	$\longmapsto$	()
  L	$\longmapsto$	(E)
  E	$\longmapsto$	S
  E	$\longmapsto$	E , S

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

$$\Sigma \bf a$$ (1)

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. We consider the following five words over $\Sigma$

   w1	=	(a, a)
   w2	=	(a, (a, a))
   w3	=	(a), (a, a)
   w2	=	(a, ((a, a), (a, a)))
   w4	=	((a, a, a), (a))

   Which of these words belong to L? For those words which belong to L, give a leftmost derivation and a rightmost derivation.
4. Is the grammar G left recursive? If yes, construct a grammar G' which is not left recursive and which generates L. If not we define G' = G.
5. Is the grammar G' LL(1)?