Homework 2 – ECS 120
1 Required written problems
Please complete the written portion of this homework on Gradescope, in the assignment titled “HW2 written”. There, you will find the problem statements for the written portion. Please type solutions directly into Gradescope.
Your written solutions will be checked for completeness but not for correctness. To receive credit, you must make a serious attempt at all problems. See the syllabus for more information.
2 Auto-graded problems
Each problem below appears as a separate “Assignment” in Gradescope, beginning with “HW2:”.
These problems are randomized and require submitting a file named req to request a problem, then submitting a file describing an automaton. See Homework 0 for detailed instructions on randomized problems.
NFA union construction (randomized) You will be given two NFAs N1 and N2. Convert them to an NFA deciding L(N1) ∪ L(N2) using the procedure described in lecture. See Theorem 5.3.4 and Figure 5.3 in the lecture notes.
NFA concatenation construction (randomized) You will be given two NFAs N1 and N2. Convert them to an NFA deciding L(N1) ◦ L(N2) using the procedure described in lecture. See Theorem 5.3.5 and Figure 5.4 in the lecture notes.
NFA star construction (randomized) You will be given an NFA N. Convert it to an NFA deciding L(N) ∗ using the procedure described in lecture. See Theorem 5.3.6 and Figure 5.5 in the lecture notes.
NFA to DFA (randomized) You will be given a NFA N, described using the text file format for the NFA simulator. Convert it to a DFA deciding L(N) using the procedure described in lecture (the subset construction). See Theorem 6.1.2 and Figure 6.1 in the lecture notes. Note that the “names” of states in the lecture notes (for example “{1, 2}” is the name of a state in the DFA) contain characters such as { that cannot be used in the simulate, but you can use names such as 1 2 instead.
regex to NFA (randomized) You will be given a regex R. Convert it to an NFA deciding L(R) using the procedure described in lecture. See Lemma 6.2.2 and Figure 6.2 in the lecture notes.
DFA to RRG (randomized) You will be given a DFA D. Convert it to an RRG deciding L(D) using the procedure described in lecture. See Theorem 6.3.1 and Figure 6.3 in the lecture notes.
DFA majority: (randomized) On this question you will test your construction from written problem Majority on Gradescope. (So do that written problem first.) You will be given three DFAs D1, D2, D3. Convert them to a DFA D deciding L(D) = Maj(L(D1), L(D2), L(D3)).
DFA to drop NFA: (randomized) On this question you will test your construction from written problem Drop operation on Gradescope. (So do that written problem first.) You will be given a DFA D. Convert it to an NFA N deciding Drop(L(D)).
2.1 NFAs
For each problem submit to Gradescope an .nfa file with an NFA deciding the given language. These problems are not randomized, so there is no need to submit a req file.
We index strings starting at 1, so x[1] is the first symbol, and x[|x|] is the last symbol.
NFA: 0’s near end or 1 at end {x ∈ {0, 1} ∗ | x[|x| − 5] = x[|x| − 2] = 0 or x[|x|] = 1}
The NFA should have at most 10 states.
NFA: xyz {xyz ∈ {0, 1, 2} ∗ | x[|x| − 3] = 2, y has at least two 0’s, and z starts with 120}
The NFA should have at most 12 states.
3 Optional challenge problems
Please read the syllabus for a discussion of optional challenge problems. Briefly, you don’t have to submit a solution to these, and they aren’t worth any points. But, if you find any interesting, and if you think you have a solution, please email it directly to me: [email protected].
1. Let A = {0n | n is prime}. Show that A2 is not regular. Let B = A \ {00}. Do you think B2 is regular?
2. Let N = (Q, Σ, ∆, s, F) be an NFA such that L(N) ≠ ∅ and L(N) ≠ Σ*. Prove or disprove the following.
(a) (∃x ∈ L(N)) |x| ≤ |Q|.
(b) (∃x ∈ L(N)) |x| ≤ |Q|.
3. Show that for every infinite regular language L, there are two infinite regular languages A and B such that A ∩ B = ∅ and A ∪ B = L.
4. Define a subsequence of a string x = x[1]x[2] . . . x[|x|] to be a string of the form x[i1]x[i2] . . . x[ik], where 1 ≤ i1 < i2 < . . . < ik ≤ |x| are all integers. (Like a substring, a subsequence consists of some symbols from x in their original order; unlike a substring, they do not have to be ad-jacent in x.) For example, if x = 010, then its subsequences are ε, 0, 1, 01, 10, 00, 010, whereas 00 is not a substring of x. Write y ⪯ x if y is a subsequence of x, and y ≺ x if y ⪯ x and y ≠ x. Let A be a language and define SS(A) = {y | y ⪯ x and x ∈ A} to be the set of all subsequences of strings in A. It is straightforward to show that if A is regular, then SS(A) is regular. (The construction is similar to the one for closure under Drop above.)
Show the following stronger result: for all languages A, SS(A) is regular!
Use the following theorem (it is not easy to prove, but just assume it is true for this exercise):
For every infinite language A, there are x, y ∈ A such that x ≺ y.