5.2 PARSING AND AM 145 4. Show that every s-grammar is unambiguous. s. Let G (V.T S, P) be an s-granamar. Give an expremion for the maximum size of P in terms of IVI and ITI. 6. show that the following grammar is ambiguous. A alAa. (7. Construct an unam grammar equivalent to the grammar 6. biguous in B. Give the derivation tree for (((a 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 expres. sions on 11. Is it possible for a regular grammar to be ambi 12. Show that the language L E (a,b) is not inherently ambigu- 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 ablbblb 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 aabbababl n the language generated by the grammar S assib? 19. Show that the grammar in Example 1.14 is unambiguous. 20. Prove the following result. Let G (V, T, S, P) be a context-free grammar im which every A E V occurs on the left side of at most one production. Then G is unambiguous. conditioni 21. grammar equivalent to that in Example 5.5 that satisfies the Find a of Theorem 5.2