homomorphism.
4. Show that the family of linear languages is closed under homomorphism.
5. Show that the family of context-free languages is closed under reversal.
6. Which of the language families we have discussed are not closed under
reversal?
7. Show that the family of context-free languages is not closed under difference
in general, but is closed under regular difference, that is, if L 1 is context-free
and L 2 is regular, then L 1 – L 2 is context-free.
8. Show that the family of deterministic context-free languages is closed under
regular difference.
9. Show that the family of linear languages is closed under union, but not closed
under concatenation.
10. Show that the family of linear languages is not closed under intersection.
11. Show that the family of deterministic context-free languages is not closed
under union and intersection.
12. Give an example of a context-free language whose complement is not
context-free.
*13. Show that if L 1 is linear and L 2 is regular, then L 1 L 2 is a linear language.
14. Show that the family of unambiguous context-free languages is not closed
under union.
15. Show that the family of unambiguous context-free languages is not closed
under intersection.
16. Let L be a deterministic context-free language and define a new language L 1
= {w : aw ε L, a ε Σ}. Is it necessarily true that L 1 is a deterministic contextfree language?
17. Show that the language L = {a n b n : n ≥0, n is not a multiple of 5} is contextfree.
18. Show that the following language is context-free.
L = {w ε {a, b}* : n a (w)= n b (w); w does not contain a substring aab}.