3. Find an s-grammar for L = {a n b n+1 : n ≥ 2}.
4. Show that every s-grammar is unambiguous.
5. Let G = (V, T, S, P) be an s-grammar. Give an expression for the maximum
size of P in terms of |V| and |T|.
6. Show that the following grammar is ambiguous.
7. Construct an unambiguous grammar equivalent to the grammar in Exercise 6.
8. Give the derivation tree for (((a + b) * c)) + a + b, using the grammar in
Example 5.12.
9. Show that a regular language cannot be inherently ambiguous.
10. Give an unambiguous grammar that generates the set of all regular
expressions on Σ = {a,b}.
11. Is it possible for a regular grammar to be ambiguous?
12. Show that the language L = {ww R : w ∈ {a,b} * } is not inherently
ambiguous.
13. Show that the following grammar is ambiguous.
14. Show that the grammar in Example 5.4 is ambiguous, but that the language
denoted by it is not.
15. Show that the grammar in Example 1.13 is ambiguous.
16. Show that the grammar in Example 5.5 is unambiguous.
17. Use the exhaustive search parsing method to parse the string abbbbbb with
the grammar in Example 5.5. In general, how many rounds will be needed to
parse any string w in this language?
18. Is the string aabbababb in the language generated by the grammar S →
aSS|b?
19. Show that the grammar in Example 1.14 is unambiguous.