Next: Exercise 2 Up: The Assignment Previous: The Assignment

## Exercise 1

We consider the grammar G with
• the four terminals ( , ) , , and (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 S L L () L (E) E S E E , S
Let be the alphabet consisting of the four terminals of G. Hence

 = {(, ), ,, } (1)

Let L be the language over 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
 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)?

Next: Exercise 2 Up: The Assignment Previous: The Assignment
Marc Moreno Maza
2004-12-01