COM S 331: Theory of Computing, Summer 2021
Homework Assignment 2
Due at 11:59PM, Wednesday, May 26, on Gradescope.
Problem 5 (20 points). Give the state diagram of a DFA that recognizes the language L = {x ∈
{0, 1}∗|x contains 101011}.
Solution
1 0 1 0 1 1
10
0 1
0
0, 1
0
Problem 6 (20 points). Give the state diagram of a DFA that recognizes the language L = {x ∈
{0, 1}∗| the binary interpretation of x is divisible by 4 } For example, �, 0, 00, 100, 1000 ∈ L. Hint:
find the commonality among strings whose binary interpretation is divisible by 4.
Solution Essentially, state n represents that when divided by 4 the current remainder is n. This
is similar to the example in lecture. Instead of being divisible by 3, where the transitions were
defined by δ(n, a) = (2n + a)mod3, here we have δ(n, a) = (2n + a)mod4. For example with the
string ”100”, starting at state 0, reading in the first ”1” will reach state 1 as ((2*0)+1)mod4=1,
then reading in the next ”0” will reach state 2 as ((2*1)+0)mod4=2, and then the transition of the
next ”0” is ((2*2)+0)mod4=0.
1
0 1 3
2
1 1
1
0
00
0
1
Also, another interesting observation is that any string ending with ”00” is divisible by 4, therefore
this language is also the same as {x ∈ {0, 1}∗ |x ends with 00 or does not contain 1}, so you can
actually have a even smaller DFA to describe this language.
Problem 7 (20 points). Convert the following NFA to an equivalent DFA using subset construc-
tion. Remove the unreachable states in your final answer.
b
a
c
d
0
1
11
1
0
Solution Let the given NFA be N = (Q,Σ, δ, s, F ). With subset construction, we can construct a
DFA M = (Q′,Σ′, δ′, s′, F ′) such that L(N) = L(M). Then Q′ = P (Q) where P (Q) is the power set
of Q, Σ′ = Σ, s′ = s, F ′ = {R |R ∈ Q′ where R contains an accept state of N}, and the transition
function will be defined as below.
0 1
{a} {a,b} {c}
{b} ∅ {d}
{c} ∅ {d}
{d} ∅ {d}
{a,b} {a,b} {c,d}
{a,c} {a,b} {c,d}
{a,d} {a,b} {c,d}
{b,c} ∅ {d}
0 1
{b,d} ∅ {d}
{c,d} ∅ {d}
{a,b,c} {a,b} {c,d}
{a,b,d} {a,b} {c,d}
{b,c,d} {b} {c,d}
{a,b,c,d} {a,b} {c,d}
{} or ∅ ∅ ∅
2
a
b
c
da, b
a, c a, d b, c b, d a, b, c
∅
b, c, d a, b, c, d
cd
a, b, d
0
1
0
1
0
1
1
0
0, 1
0
0
10
0
0
0
1
0
0
1 1 1
1
10
1
1 1
1
As you can see there is no path from the start state to the states in the lower part of the state
diagram, they’re hence called unreachable states. After removing all these unreachable states, you
will get a much smaller DFA as below. Assume all missing transitions to lead to a trash state (which
is represented by state ∅ earlier).
a
a, b
c
c, d
d0
1
0
1
1
1
1
Problem 8 (20 points). Prove that �-NFAs are equivalent to DFAs.
Solution Short answer for this is the proof for Theorem 1.39 in our textbook shows that every
NFA (including �-NFA) has an equivalent DFA, thus �-NFAs are equivalent to DFAs.
Problem 9 (20 points). Minimize the following DFA.
3
b d f
a c e
1 1
0, 1
0 0
0
1
01
0 1
Solution
ab cde f
0
1
0
1
0, 1
4