Exercise 3.

Let $\Sigma$ be the alphabet consisting of the opening parenthesis, the closing parenthesis, the comma and the lower-case letter a. That is $\Sigma$ = {(, ), ,, $\bf a$}. Let G be the grammar over $\Sigma$, with non-terminals S, L, E, start symbol S and the six productions below

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

Let $\cal {L}$ be the language over $\Sigma$ generated by G. For each of the words below, if it belongs to $\cal {L}$, then give a derivation from S to this word.

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

Answer 3