Exercise 7(a) above. For the definition of head see Exercise 18, Section 4.1.
11. Find a context-free grammar for Σ = {a, b} for the language L = {a n ww R b n :
w ∈ Σ * , n ≥ 1}.
*12. Given a context-free grammar G for a language L, show how one can
create from G a grammar so that L
= head (L).
13. Let L = {a n b n : n ≥ 0}.
(a) Show that L 2 is context-free.
(b) Show that L k is context-free for any given k ≥ 1.
(c) Show that and L * are context-free.
14. Let L 1 be the language in Exercise 8(a) and L 2 the language in Exercise
8(d). Show that L 1 ∪ L 2 is a context-free language.
15. Show that the following language is context-free.
*16. Show that the complement of the language in Example 5.1 is context-free.
17. Show that the complement of the language in Exercise 8(c) is context-free.
18.
Show
that
the
language
with Σ = {a,b,c},is
context-free.
19. Show a derivation tree for the string aabbbb with the grammar
Give a verbal description of the language generated by this grammar.
20. Consider the grammar with productions