Problem 1

Consider the following grammar:

• S → cAc
• A → AcA
• A → aa
• A → bb

Find derivations for the strings caacbbcbbc and cbbcaacaacaac.

Problem 2

Can Context Free Grammars express everything that regular exrpessions can? Here's a list of some of the languages defined by regular expressions. See if you can write context free grammars generating them.

1. (a|b)*, i.e. any string over {a,b}
2. a(a|b)*b, i.e. any string that starts with a and ends with b
3. abb|bba, i.e. {abb,bba}

Problem 3

Can Context Free Grammars express languages that cannot be expressed by regular expressions? Here's a list of some of the languages we proved are not regular, i.e. cannot be accepted by finite automata. See if you can write context free grammars generating any of them. Note: some are not possible!

1. {aⁿbⁿ | n ≥ 0}
2. {aⁿbⁿcⁿ | n ≥ 0}
3. The language of properly parenthesized lists of a's
4. The language of palindromes over {a,b,c}
5. The language of all strings of a's whose length is prime