Problem
Consider the grammar
S → A S U | N A U
A → a A | ε
N → a N b| a | b
U → u U| ε
Assume that the conventions we discussed in class for writing grammars are followed.
A. What is the start symbol? Explain briefly. No explanation, no credit!
B. What are the non-terminals? Explain briefly. No explanation, no credit!
C. What are the terminals? Explain briefly. No explanation, no credit!
D. Give two different left-most derivations for the input:
a a a b b a u
The first left-most derivation should start with S => A S U
The second left-most derivation should start with S => N A U
• In the left-most derivation of
a a a b b a u
that starts with S => N A U, which part of the input corresponds to the N? which part of the input corresponds to the A and which part of the input corresponds to the U? You answer should have the following format:
The part of input that corresponds to the first N is ...
The part of input that corresponds to the A is ...
The part of input that corresponds to the second U is ...
where the "...". is replaced by a substring of the input. Concatenated together, they form the whole input.
• What is the language of this grammar (remember that the language of a grammar is the set of strings that can be derived from the start symbol or, equivalently, the set of strings that have parse trees according to the grammar). In your description of the language, you should try to be as precise but as brief as possible.