Questions: 4, 11 a) d), 12, 14, a) b), 21

Chapter 1 INTRODUCTION TO THE THEORY OC 28 aaoahonad, baaaabaanab, baaoaabaa? Which strings are in L4 5. Let = {a, b} and L-(aa, bb). Use set notation to describe T. 0. Let 1, be any langunge on a nonmptyalphabet. Show that L and 4 Let L- (ab, aa, baa). Which of the following strings are in L': abra ca both be finite. T. Are there languages for which 8. Prove that (T).? for all languages Li and L 9. Show that (L")" L" for all languages. 10. Prove or disprove the following claims (a) (Li u Laj" = Le u L for all languages L1 and L2. (b) (LR). = (L')" for all languages L. 11. Find grammars for -{a,b) that generate the sets of (a) all strings with exactly one a. (b) all strings with at least one a (c) all strings with no more than three a's. (d) all strings with at least three a's. In each case, give convincing arguments that the grammar you give does indeed generate the indicated language 12. Give a simple description of the language generated by the grammar with productions SA. 13. What language does the grammar with these productions generate? 14. Let = {a, b). For each of the following languages, find a grammar that generates it