3. Give a derivation tree for w = abbbaabbaba for the grammar in Example 5.2.
Use the derivation tree to find a leftmost derivation.
4. Show that the grammar in Example 5.4 does in fact generate the language
described in Equation 5.1.
5. Is the language in Example 5.2 regular?
6. Complete the proof in Theorem 5.1 by showing that the yield of every partial
derivation tree with root S is a sentential form of G.
7. Find context-free grammars for the following languages (with n ≥ 0, m ≥ 0).
(a) L = {a n b m : n ≤ m + 3}.
(b) L = {a n b m : n ≠ m − 1}.
(c) L = {a n b m : n ≠ 2m}.
(d) L = {a n b m : 2n ≤ m ≤ 3n}.
(e) L = {w ∈ {a, b} * : n a (w) ≠ n b (w)}.
(f) L = {w ∈ {a, b} * : n a (v) ≥ n b (v), where v is any prefix of w}.
(g) L = {w ∈ {a,b} * : n a (w) = 2n b (w) + 1}.
8. Find context-free grammars for the following languages (with n ≥ 0, m ≥ 0, k
≥ 0).
(a) L = {a n b m c k : n = m or m ≤ k}.
(b) L = {a n b m c k : n = m or m ≠ k}.
(c) L = {a n b m c k : k = n + m}.
(d) L = {a n b m c k : n + 2m = k}.
(e) L = {a n b m c k : k = |n − m|}.
(f) L = {w ∈ {a, b, c} * : n a (w) + n b (w) ≠ n c (w)}.
(g) L = {a n b m c k , k ≠ n + m}.
(h) L = {a n b m c k : k ≥ 3}.
9. Show that L = {w ∈ {a,b,c} * : |w| = 3n a (w)} is a context-free language.
10. Find a context-free grammar for head (L), where L is the language in