Problem 1. Consider the grammar
S -> AB
A -> BaA | bB
B -> aSB | AS | e
1. Show that this grammar is ambiguous by constructing two different leftmost derivations for the sentence abab
2. Show that this grammar is ambiguous by constructing two different parse tress for the string abab
Problem 2. Compute FIRST sets for the following grammar.
S -> aAB | CD
A -> CD | SE | e
B -> aSB | AS
C -> cC | e
D -> CDd | e
E -> eFg
F -> Fg | e
Problem 3. Design a regular expression called FOO to capture the following English description: all strings that start with alternating as and bs (no as or bs next to each other), followed by an even number of at least two cs, and ending with either any number of bs or a single a. Show that your regular expression is correct by showing strings that are in the language and strings that are not in the language.