Description
Problem 1 (20 points)
Let Σ = {0, 1}. Construct a DFA A that recognizes the language
that consists of all binary numbers that can be divided by 5. For
example, A should accept 101, 1010, 1111 etc, and should reject
010, 111, 1110 etc. Justify your answer.
Note: Your DFA should have no more than 5 states.
2 / 6
CS 331: Theory of Computing
Problem 2 (20 points)
Let w = σ1 · · ·σn be a word on an alphabet Σ. By w
R we mean
the word σn · · ·σ1. Define L R such that
L R = { w ∈ Σ
∗
| w
R
∈ L }.
Prove that if L is regular, then so is L R.
3 / 6
CS 331: Theory of Computing
Problem 3 (20 points)
Let Σ = {0, 1}. We use kwkw0 to denote the number of occurrences
of the subwords w
0
in w. Construct a DFA that recognizes the
following language:
{ w ∈ Σ
∗
| kwk10 = kwk01 } .
4 / 6
CS 331: Theory of Computing
Problem 4 (20 points)
For language L1 and L2, let the imperfect shuffle of L1 and L2
be the language
{ w ∈ Σ
∗
| w = w1v1 · · · wk vk ,
w1 · · · wk ∈ L1, v1 · · · vk ∈ L2, wi
, vi ∈ Σ
∗
} .
Prove that the class of regular languages is closed under imperfect
shuffle.
5 / 6
CS 331: Theory of Computing
Problem 5 (20 points)
An NFA A = (Q, Σ, q0, δ, F) is called co-deterministic (CDFA) if
for any a ∈ Σ and any two distinct states q and q
0
,
δ(q, a) ∩ δ(q
0
, a) = ∅.
Prove or disprove the following statements.
Every CDFA is a DFA. (5 points)
Every DFA is a CDFA. (5 points)
Every NFA can be converted to an equivalent CDFA. (10 points)
Hint: A CDFA can be viewed as a DFA as if the word is read from
the end to the beginning. Your solution to Problem 2 may help.
6 / 6
CS 331: Theory of Computing
