CS 334: Problem Set 5

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
′
𝑠}