CSE 105 Homework 4
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CSE 105
Homework 4
2022
1. (10 points) A common misconception about regular languages is that if a language is regular, then its subsets or supersets must be too. In this question, you will show that this is false. Let Σ be some fixed alphabet.
a. Give an example of a regular language X that is a subset of all nonregular languages over Σ . Briefly justify your answer.
b. Give an example of a regular language Y that is a superset of all nonregular languages over Σ . Briefly justify your answer.
c. Give an example of sets A,B,C such that A ⊂ B ⊂ C and A and C are nonregular but B is regular. Briefly justify your answer. For this part of the problem, you may assume that Σ has at least two symbols.
For each part of this problem, justify any claims you make about certain sets being regular or nonregular either by proving the claim from definitions or citing a fact proved in class or in the textbook.
2. (6 points) Minimum pumping length: (Sipser 1.55) The pumping lemma says that every regular language has a pumping length p such that every string in the language can be pumped if it has length p or more. If p is a pumping length for language A, so is any length p\ ≥ p. The minimum pumping length for A is the smallest positive integer p that is a pumping length for A. For the language described by each of the regular expressions below, find the minimum pumping length and justify your answer.
(a) {0}
(b) (11)* 01*
(c) 0010 n 0* 1*
3. (9 points) Go to http://regexcrossword .com/ and go through the“how to play”and “tutorial”pages to learn how to play Regular Expressions Crossword puzzles. You may want to go through the “Beginner”, “Intermediate” and “Experienced” puzzles for extra fun/practice.
Then, go to http://regexcrossword.com/challenges/palindromeda/puzzles/3 (the third of the “Palin- dromeda” puzzles). Solve it, validate your answer, and submit a screenshot of your solution.
Figure 1: The crossword
4. (15 points) Consider the language
L = {wtwR | w ∈ {0, 1}+ and t ∈ {1}+ }.
a. Prove that L is not regular.
b. Prove that L is context-free by providing a CFG with eight or fewer productions that generates it. Informally explain why the CFG you provide works. Note: the abbreviation A → 0A1 | B counts as two productions .
5. (10 points) Consider the language L over the alphabet Σ = {a,b}
L = {u ∈ {a,b}* | the number of‘a’characters in u is exactly twice the number of‘b’characters in u}
For example, ε,aab,bbaaabaaa are all strings in L.
a. Prove that L is context-free by giving a CFG that generates it. Informally explain why the CFG you provide works.
b. Is the CFG you gave in part a. ambiguous? Why or why not?
2022-10-28