CS/ECE 374 A (Spring 2022) Homework 3 Solutions
Problem 3.1: For each of the following languages in parts (a), (b), and (c), describe an NFA that accepts the language, using as few states as you can. Provide a short explanation of your solution. Below, #0(x) and #1(x) denote the number of 0’s and the number of 1’s in x respectively.
(a) (30 pts) all strings x ∈ {0,1}∗ such that (x ends with 10101 or 11011) and (#0(x) is divisible by 3 or #1(x) is divisible by 3).
(b) (30 pts) the language defined by the regular expression ((01)∗0+2)(100)∗1∗ ·(1∗ +0∗2∗) over the alphabet {0, 1, 2}.
Copyright By PowCoder代写 加微信 powcoder
(c) (10 pts) all strings in {0, 1}∗ that contains the pattern 0?1?0, where “?” denotes “don’t care” (i.e., a single symbol that is either 0 or 1); in other words, the language defined by the regular expression (0 + 1)∗ · 0(0 + 1)1(0 + 1)0 · (0 + 1)∗.
(d) (30 pts) Convert your NFA from part (c) to a DFA by using the subset construction (i.e., power set construction). [Note: don’t include unreachable states; also, several accepting states can be collapsed into one in this DFA.]
a e f g h acc 0
Explanation:
The part from s1 accepts all strings that end with 10101 and have number of 0’s divisible by 3 (if we exit the cycle s1ab via transition from a to e), or end with 11011 and have number of 0’s divisible by 3 (if we exit the cycle s1ab via the transition from b to i).
Similarly, the part from s2 accepts all strings that end with 10101 and have number of 1’s divisible by 3 (if we exit the cycle s2cd via the transition from s2 to e), or end with 11011 and have number of 1’s divisible by 3 (if we exit the cycle s2cd via the transition from d to i).
We take the union by having ε-transitions from s to s1 and to s2.
[Note: we will not deduct points if you use a small number of extra states, e.g., if you didn’t reuse states in the two parts from s1 and from s2. But we will deduct points if you use a product construction, which would increase the number of states drastically.]
0,1 ABCDEF
Explanation: We follow the recursive algorithm from class, taking a few obvious shortcuts and eliminating some of the unnecessary ε-transitions. For example, the states a,b correspond to (01)∗ and states c, d, e correspond to (100)∗, and so the states s, a, b, c, d, e correspond to ((01)∗0+2)(100)∗1∗. To get to f, we append 1∗. To get to h, we append 0∗2∗.
[Note: we will not deduct points for keeping some of the extra ε-transitions—sometimes, it’s safer to include them.]
0 0,1 1 0,1 0
Explanation: A is the start state, B means that the string ends with 0, C means the string ends with 0?, D means the string ends with 0?1, E means the string ends with 0?1?, and F means the string contains 0?1?0.
A AB ABC ACD ABE acc
[Note: in the above, we have collapsed all states whose subsets contain F into a single state “acc”, because once we have reached such a state, we will accept regardless of the remainder of the input string, for this language. We will not deduct points if you don’t collapse them, though the number of states would increase.]
Problem 3.2: Given a language L over the alphabet Σ, define
move-back8(L) = {xayz : xyaz ∈ L, x,y,z ∈ Σ∗, a ∈ Σ, |y| ≤ 8}.
Prove that if L is regular, then move-back8(L) is regular.
(For example, if 010010100110011 ∈ L, then 011001010010011 ∈ move-back8(L).)
[Hint: given an NFA (or DFA) for L, construct an NFA for move-back8(L). Give a formal description of your construction. Provide an explanation of how your NFA works, including the meaning of each state. A formal proof of correctness of your NFA is not required.]
Solution: Let L be a regular language over Σ = {0,1}. By Kleene’s theorem, L is accepted by some DFA M = (Q,Σ,s,δ,A). We construct an NFA M′ = (Q′,Σ,s′,δ′,A′) accepting move-back8(L) (which would imply that move-back8(L) is regular by Kleene’s theorem). The construction is as follows:
Q′ = {(q,before):q∈Q} ∪
{(q,a,i,middle) : q ∈ Q, a ∈ Σ, i ∈ {0,1,…,8}} ∪ {(q, after) : q ∈ Q}
s′= (s, before)
A′= {(q,after):q∈A}
δ′((q, before), a) = δ′((q, a, i, middle), b) =
δ′((q, a, 8, middle), b) = δ′((q, after), a) =
{(δ(q, a), before),
(q, a, 0, middle),
(δ(q,a),after)} ∀q ∈ Q, a ∈ Σ
{(δ(q, b), a, i + 1, middle),
(δ(δ(q,b),a),after)} ∀q ∈ Q, a,b ∈ Σ, i ∈ {0,…,7} {(δ(δ(q, b), a), after)} ∀q∈Q, a,b,∈Σ
(δ(q, a), after) ∀q∈Q, a∈Σ
(The number of states is clearly finite: |Q′| = 2|Q| + 9|Q||Σ|.)
Explanation: The idea is to divide the process into three phases: before (reading the prefix x), middle (reading the substring ay), and after (reading the suffix z). We use nondeter- minism to guess when to switch from the before phase to the middle phase, and when to switch from the middle phase to the after phase. At the same time, we simulate M on the string xyaz.
Meaning of states in M′:
M′ may be in state (q,before) after reading input w iff M may be in state q after
reading input w.
M ′ may be in state (q, a, i, middle) after reading input w iff M may be in state q after
reading input xy for some strings x, y with w = xay with |y| = i.
M ′ may be in state (q, after) after reading input w iff M may be in state q after reading
input xyaz for some strings x, y, z with w = xayz with |y| ≤ 8.
Remark: Alternatively, using ε-transitions, we may define δ′ slightly more simply as follows:
δ′((q, before), a) δ′((q,a,i,middle),b)
δ′((q, a, i, middle), ε) δ′((q, after), a)
= {(δ(q, a), before),
(q,a,0,middle)} ∀q ∈ Q,
= {(δ(q,b),a,i+1,middle)} ∀q∈Q, = {(δ(q, a), after)} ∀q ∈ Q, = (δ(q, a), after) ∀q ∈ Q,
a,b∈Σ, i∈{0,…,7} a,b ∈ Σ, i ∈ {0,…,8} a∈Σ
[Note: There are also more complicated solutions that “remember” the last 8 characters read, but this would increase the number of states quite a bit.]
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com