Class Work 14: Pumping Lemma for Context Free Languages

Computer Science 416/685: Computability Theory
Lehman College, City University of New York
Fall 2016

Grading Notes:

• Submit one answer per group.
• Make sure that the answer is legible.
• Include the full names of all group members on your submitted work (so all get credit).

Recall that a palindrome is a word that is the same written forward or backwards (i.e. w^R = w).

1. Show that the language of all palindromes over {0,1} is not a regular language.
2. Show that the language of all palindromes over {0,1} is a context-free language.
3. Show that the language of all palindromes over {0,1} containing an equal number of 0's and 1's is not a context-free language.