## Description

CS 334: Problem Set 5.

Problem 1. (10 points) Use the pumping lemma to prove that the language {0

2

?

: ? ≥ 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

′

?}