CSE 105 Winter 2023 Homework 3
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CSE 105 Winter 2023
Homework 3
Due date: Tuesday, January 31 2023 at 11:59pm
1. Let X be a language. Define the function T applied to X as T (X) = {u 。v | u e X and v e X}. In this problem, we will prove that the class of regular languages over the alphabet {a, b} is closed under the function T.
(a) Fill in the blanks of the following proof:
Setup Let A be a regular language over the alphabet Σ = {a, b}. Then let M be a DFA that recognizes the language A, i.e., L(M) = A such that M = (Q, Σ, δ, q0 , F).
Construction Build a new NFA whose language is T (A). I will give you all the parts except for the transition function. You will have to fill that in.
The main idea is to build two copies of M (a first copy (1) and a second copy (2)) and connect the accept states of the first copy to the start state of the second copy with spontaneous transitions and make the start state the same as the start state from the first copy and the accept states will be the accept states from the second copy.
N = (Q × {1, 2}, {a, b}, δ\ , (q0 , 1), F × {2})
(no justifications necessary.)
|
δ \ ( ((q, 1), x) ) = |
if q e Q and x e {a, b} |
|
δ \ ( ((q, 2), x) ) = |
if q e Q and x e {a, b} |
|
δ \ ( ((q, 1), ε) ) = |
if q e F |
|
δ \ ( ((q, 1), ε) ) = |
if q |
|
δ \ ( ((q, 2), ε) ) = |
if q e Q |
(b) Draw a DFA that recognizes the language L(a* b* )
(c) Use the construction above to construct an NFA that recognizes the language T (L(a* b* )).
(d) Describe T (L(a* b* )) using a regular expression.
2. Let w be a string over the alphabet {0, 1}.
Let A be a language over the alphabet {0, 1} and let
DoubleStart(A) = {w1 w1 w2 . . . wn | w1 w2 . . . wn e A and n > 1}
Essentially, Doublestart(A) creates a set that is the result of doubling the first character for all strings of A. Note that ε 
DoubleStart(A) for any language A since there is no first character of ε to double.
In this problem, we will prove that the class of regular languages over the alphabet {0, 1} is closed under the function DoubleStart.
(a) Write out the setup and construction stages for this proof.
(You can start the setup with a DFA and you can construct an NFA in the construction.)
(b) Describe the language of this DFA:
(c) Apply the construction to the DFA above:
3. Consider the regular expression: b(a n (ab)* )(a n bb)* ab
Create an NFA that recognizes the language of the regular expression.
4. Let X be a language over {0, 1}.
Define the function ZeroSandwich(X) = {0 x0nn | x e X, n > 0}
(a) Show that the class of regular languages is NOT closed under the function ZeroSandwich.
(Hint: use the pumping lemma.)
(b) Show that the class of non-regular languages is NOT closed under the function ZeroSandwich. (Hint: prove that {02k | k > 0} is a non-regular language using the pumping lemma and use it as a counter-example.)
2023-02-02