(d) (e) (f)
CS/ECE 374 A (Spring 2022) Midterm 1 Solutions
False. A counterexample: 11010 is accepted by the DFA but is not generated by 0∗(11)∗10(0 + 1)∗.
[Note: a correct regular expression for this DFA would be (0 + 11)∗10(0 + 1)∗.] True. By Kleene’s theorem, every regular language is recognized by some DFA.
Copyright By PowCoder代写 加微信 powcoder
[Alternative explanation: in class, we have shown how to convert regular expressions to NFAs (by a recursive algorithm), and from NFAs to DFAs (by the subset or power-set construction).]
True. By the subset of power-set construction, L is accepted by a DFA with at most 2n states. And the complement of L is accepted by a DFA with the same number of states (by switching the role of accepting and rejecting states).
False. A counterexample is L1 = {1} and L2 = {0}. Here, 11 is in (L1 ∪ L2)∗ but not in ( L ∗1 L 2 ) ∗ .
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)∗!
False. One counterexample is L = {0n2 : n ≥ 0}, with Σ = {0}. Here, L is not regular (asshowninthelabs),but{xyz:x∈{0}∗, y∈L, z∈{0}∗}isexactly0∗ andsois regular.
[Another counterexample is L = {wwR : w ∈ {0,1}∗,|w| ≥ 374} (with Σ = {0,1}∗). Here, L is not regular, but in a homework problem (Problem 4.1(c)), you have already shown that {xwwRz : x, w, z ∈ {0, 1}∗, |w| ≥ 374} is regular!]
False. The minimum fooling set size is equal to the minimum number of states over all DFAs accepting the language, but this language has a DFA with 2022 states.
[Alternatively, one can argue directly: if there is a fooling set F of size 2023, there must exist two distinct strings x, y ∈ F with x ≡ y mod 2022 by the pigeonhole principle. But x and y are indistinguishable, since for any z, |xz| is divisible by 2022 iff |yz| is divisible by 2022.]
True. This is stated in class (we can convert any regular expression to a CFG directly, or alternatively, any DFA to a CFG).
True. The grammar generates 0∗1+, 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 : first 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.]
(05)∗(15)∗ + 0(05)∗1111(05)∗ + 00(05)∗111(05)∗ + 000(05)∗11(05)∗ + 0000(05)∗1(05)∗. Define the following DFA M = (Q, {0, 1}, s, δ, A):
Q = {i:0≤i≤2022}∪{(i,k):1≤i≤2022,0≤k