Show that the string aabbabba is not in the language generated by this
grammar.
21. Consider the derivation tree below.
Find a grammar G for which this is the derivation tree of the string aab.
Then find two more sentences of L(G). Find a sentence in L(G) that has a
derivation tree of height five or larger.
22. Define what one might mean by properly nested parenthesis structures
involving two kinds of parentheses, say () and []. Intuitively, properly nested
strings in this situation are ([]), ([[]])[()], but not ([)] or ((]]. Using your
definition, give a context-free grammar for generating all properly nested
parentheses.
23. Find a context-free grammar for the set of all regular expressions on the
alphabet {a, b}.
24. Find a context-free grammar that can generate all the production rules for
context-free grammars with T = {a, b} and V = {A, B, C}.
25. Prove that if G is a context-free grammar, then every w ∈ L(G) has a
leftmost and rightmost derivation. Give an algorithm for finding such
derivations from a derivation tree.
26. Find a linear grammar for the language in Example 5.3.
27. Let G = (V,T,S,P) be a context-free grammar such that every one of its