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

โฒ

๐ }

Sale!