Sale!

CS 334: Problem Set 5

$30.00

Category:
Rate this product

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
โ€ฒ
๐‘ }

Open chat
Need help?
Hello
Can we help you?