Problem 1. (10 points) Use the pumping lemma to prove that the language {02 : ≥ 0} is not
regular. The language consists of strings of 0’s whose lengths are powers of 2. Be sure to include all details of your proof.
Problem 2. (10 points) Prove that the language = {0 1 : ≠ } is not regular. Do not use the
pumping lemma. Instead, consider how is related to the non-regular language {0 1 : ≥ 0}.
Problem 3. (10 points) The pumping lemma says that every regular language has a pumping length , such that every string in the language can be pumped if it has length or greater. If is a pumping length for regular language , then so is any length ′ ≥ . The minimum pumping length for is the smallest that is a pumping length of .
For example, the pumping length of 01∗ cannot be 1 because the string = 0 of length 1 cannot be pumped to give another string in the language. But, any string of length 2 or more can be pumped by choosing = 0, = 1, to be the rest of the string.
What is the minimum pumping length for each of the following languages? Justify your answer in each case.
1. 0001∗
2. 0∗1∗
3. 0∗1∗0∗1∗ ∪ 10∗1
4. (01)∗
5. 1∗ 01∗ 01∗
Problem 4. (10 points) Give context-free grammars that generate the following languages (the alphabet in each case is {0,1}):
1. { : = }, the language of palindromes
2. { : ℎ ℎ }
3. { :0′ ℎ 1′ }
