Required:

Give CFG's for the following languages:

1. L={ww^r}
2. L={w | w = w^r}  How does this language differ from #1?
3. L={a^2nb^n}
4a. Set of strings with more 0's than 1's
4b. L={a^nbc^n}
4c. L={a^nb^xc^y, x+y=n}
4d. L=O(0+1)*(11)*
4e. Set of strings where each sequence of a's is followed by
    an equal number of b's. Interpret this to mean that
    abbbab is not in L (so you can't partition long sequences
    of b's into two substrings). 
4f. Set of strings where each sequence of a's is followed by at
    least as many b's
4g. L=(00)*1(00)*00
4h. L = odd length strings 

5. Let S -> aS | aSbS | empty
   Derive and show a parse tree for aaabaa

Describe a PDA to accept the following:

6. strings w with equal number of 0's and 1's such that
   w begins and ends with a 0.

7. The language of 4c and for 4f

8. The language generated by 
   S -> aAA
   A -> aS | bS | a

9. Put the following into Chomsky Normal Form:

S -> ABC | e
A -> Ba | A
B -> b | AB | AaB
C -> Cc | c


Optional: 7.1.2


4c. Solution:  S -> T | e
               T -> aTc | B
               B -> aBb | e

4a. Solution:  S -> T0S | T0T
               T -> 0T0T | 1T1T | e