Assignment IV

Due date Oct.15.

1. Consider the grammar:

S => ( L ) | a
L => L, S | S

where the terminals are { ( ) , a}
Build parse trees for the following sentences in the language:

a) (a, (a, a))

b) (a, ((a, a), (a, a)))

c) Describe informally the language generated by this grammar.

2. Give context-free grammars for the following languages, defined over the alphabet {0, 1}:

a) {w | w contains more 1's than 0's}

b) the complement of the language {1^n 0^n | n >= 0}, that is to say all the strings that DO NOT consist of a number of 1's followed by the same number of 0's.

3. To understand how a predictive parser work, let's use the parse table we described in class to trace the functioning of the automaton over the sentence

(a + b) * (c * d)

We describe each step of the process by displaying the contents of the stack, the input that remains, and the production that we use to go to the next step. At the beginning, the stack contains the marker $ and the sentence symbol. Here are the first two steps:

stack............input......................... production
$E.............(a + b) * (c * d)$............E -> TE'
$E'T.........(a + b) * (c * d)$............T -> FT'

Fill in the rest of the table, until both stack and input contain only $.

4. a) Remove the left-recursion from the grammar in question 1, and compute the FIRST and FOLLOW sets for the new grammar, as described in class.

b) Build the parse table for the resulting language, and trace the functioning of the resulting automaton on the first sentence in question 1.

5. Consider the following grammar, which generates expressions in prefix form over the variables x and y:

E -> +EE | *EE | -EE | x | y
a) Give leftmost and rightmost derivations for the string: +*-xyxy

b) Prove as convincingly as you can that this grammar is unambiguous.

6. From text: problem 2.8 (ambiguity in natural language).