next up previous
Next: Exercise 4. Up: Quiz5 Previous: Exercise 2.

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  
\fbox{
\begin{minipage}{13 cm}
\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\mbox{ } \...
...\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\end{minipage}}


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