Theory of Computation HW2 Solutions (100 points total)
HW: 1.1, 1.2, 1.3, 1.5abc, 1.6abcfmn, 1.36
Note: The textbook provides answers for the following: 1.1, 1.2, 1.5ab
Some of the questions with solutions are therefore not graded at all, while others are graded to make sure they were done, but only assigned a few points.
Copyright By PowCoder代写 加微信 powcoder
Grading: 1.1 (not graded), 1.2 (5 points), 1.3 (10 points), 1.5a (5 points), 1.5b (5), 1.5c (0 points), 1.6 (60 points: 10 points each part), 1.36 is worth 15 points.
1.1 (not graded)
b. M1: F = {q2}
c. M1: q1(start)→q2→q3→q1→q1 d. M1 does not accepts aabb
e. M1 does not accept ε
M2: F = {q1, q4}
M2: q1(start)→q1→q1→q2→q4 M2 does accept aabb
M2 does accept ε
1.2 (5 points- even though answer in book)
M1 = (Q, , δ, q0, F) Q = {q1, q2, q3}
= {a, b}
M2 = (Q, , δ, q0, F) Q = {q1, q2, q3, q4}
= {a, b}
F = {q1, q4}
1.3 (10 points)
δ a b q1 q2 q1 q2 q3 q3 q3 q2 q1
δab q1 q1 q2 q2 q3 q4 q3 q2 q1 q4 q3 q4
(5 points)
b a a,b ab
(5 points)
S b ba bab baba a,b
(Not graded)
Note: in the diagram above it would be reasonable to have two separate states instead of q2, but the above diagram is more efficient. Also note that in this case it is probably easiest to do the problem directly and not construct the complement language first. If you do want to do the complement, it works as follows. The language is w contains neither ab nor ba. This is ab ba. The complement is (ab v ba). Thus you can construct ab v ba and then switch accept and non-accept states.
1.6 (60 points total: 10 points each) a)
0 S00101001010,1
S 1 11 110 a,b
(15 points)
For each n ≥ 1 we build a DFA with n states q0, q1, .., qn-1, to count the number of consecutive a’s modulo n. For each character a that is input, the counter increments by 1 and jumps to the next state in M (the last state loops back to the start state). It accepts the string if and only if the machine stops at q0. That means the
length of the string consists of all a’s and its length is a multiple of n. Formally, the set of states of M is Q={q0, …, qn-1}, q0 is the start and accept state and the transition function δ(qi,a) = qj where j=i+1 mode n. You could also define this with a diagram.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com