CIS 573 Homework, due March 27

1. For this problem, refer to the grammar in Example 5.9 (page 330).
   1. Give a derivation of bbabb from L.
   2. Give a parse tree for bbabb rooted at L.
2. For this problem, refer to the grammar in Exercise 5.6-1 (page 353).
   1. Give a derivation of bbabb from A.
   2. Give a parse tree for bbabb rooted at A.
3. Prove that
   1. the set of CFLs is closed under union
   2. the set of CFLs is closed under concatenation
   3. the set of CFLs is not closed under intersection
   4. the set of CFLs is not closed under complementation
   If you are having trouble with this problem, see pages 10, 247-249, and 280.
4. Exercises 5.1-1(a,b,c), 5.1-2, 5.2-7, 5.3-1(c,e,g,h,i,j,m), 5.5-2(b), 5.6-1, 5.6-2, 5.8-3(a,b,c)
5. A CFG is right-linear if every production is of the form of the form X -> Λ, or X -> cY. Prove that L is regular if and only if L is generated by a right-linear CFG. (Note: c denotes a terminal character.)