CS/ECE 374 A (Spring 2022) Midterm 1 Solutions
False. A counterexample: 01203 is accepted by the NFA but is not generated by 2∗0(10+ 3)∗ .
[Note: a correct regular expression for this DFA would be 2∗0(12∗0 + 3)∗, or (2 + 03∗ 1)∗ 03∗ .]
(b) True. By Kleene’s theorem, every language accepted by a DFA is regular.
Copyright By PowCoder代写 加微信 powcoder
(c) False. By reversing the direction of all transitions, the machine may become nondeter- ministic.
(d) True. Both (L1 ∪ L2)∗L∗1 and (L1 ∪ L2L∗2)∗ simplify to (L1 ∪ L2)∗.
(e) True. If x contains 0n1n as a substring for some n ≥ 374, then x contains 03741374 as a substring. The converse is trivially true. Thus, a regular expression is (0 + 1)∗ · 0374 1374 · (0 + 1)∗.
(f) True. A regular expression is (0 + 1)∗ · 5n=0{0n1n0n} · (0 + 1)∗. In fact, because n = 0 is not forbidden, the language is just (0 + 1)∗!
(g) True. The set F = {0i : 0 ≤ i < 2022} is a fooling set of size 2022. To see this, consider twodistinctx,y∈F,i.e.,x=0i andy=0j forsome0≤i,j<2022withi̸=j. Pick z = 02022−i. Then xz = 02022 is in the language, but yz = 02022−i+j is not in the language.
(h) False. A counterexample: {0n1n : n ≥ 0} is context-free but is not regular.
(i) True. The grammar generates all strings of even length, i.e., ((0+1)2)∗, which is clearly regular.
2. (c) (Cont’d) Meaning of states: s: the start state.
3. (a) (b)
0: read one 0.
1: read one 1.
XY : second-to-last symbol is X, and last symbol read is Y .
[One alternative solution is to first draw an NFA (which requires just 4 states) and then apply the subset or power-set construction. Another alternative is to build DFAs for (0 + 1)∗00 and for (0 + 1)∗11 and then apply the product construction.]
The language is L = 374 0i(1i)∗. Since 0i(1i)∗ is clearly regular for any fixed i and a i=1
finite union of regular languages is regular, L is regular. Define the following DFA M = (Q, {0, 1}, s, δ, A):
ChooseF ={0i :i≥0}.
Let x and y be two arbitrary distinct strings in F.
Thenx=0i andy=0j forsomei̸=j. Withoutlossofgenerality,assumei