CS 332: Theory of Computation Prof. Mark Bun
Boston University February 4, 2021
Homework 2 – Due Thursday, February 11, 2021 at 11:59 PM
Reminder Collaboration is permitted, but you must write the solutions by yourself without as-
sistance, and be ready to explain them orally to the course staff if asked. You must also identify
your collaborators and write “Collaborators: none” if you worked by yourself. Getting solutions from
outside sources such as the Web or students not enrolled in the class is strictly forbidden.
Problems There are 5 required problems and two bonus problems.
1. (The problem formerly known as HW1 Problem 5.) Consider the following state diagram of an
NFA N over alphabet {A,B}.
q0start
q1 q2 q3
q4 q5
ε
ε
B
A,B
A
A
B
B
A
(a) Give a formal description of the machine N as a 5-tuple.
(b) Does the machine accept the string AAB?
(c) Does the machine accept the string BBBA?
(d) Does the machine accept the string AAA?
(e) What is the language recognized by N?
2. Consider the following state diagram of an NFA N over alphabet {A,B}.
q0start q1 q2 q3
B
B
ε
A
A
(a) Consider running N on input BBA. Give examples (i) of a computation path that leads N to
an accept state when run on this input, (ii) a computation path that leads N to a reject state,
and (iii) a computation path that leads N to fail before it’s read the entire input.
1
(b) What is the language recognized by N?
(c) Use the subset construction to convert N into a DFA recognizing the same language. Give
the state diagram of this DFA – only include states that are reachable from the start state.
3. Think about, but do not hand in: A DFA or NFA can, in general, have zero, one, or many accept
states. Show that every NFA can be converted into another NFA recognizing the same language,
but which has exactly one accept state. (This is solved exercise 1.11 in Sipser if you’d like to check
your solution.)
To hand in: Prove that this is not true for DFAs. That is, show that there is a regular language
L such that every DFA recognizing L requires at least two accept states. Hint: If L contains the
empty string, what can you say about the start state of any DFA recognizing L?
4. On Monday, we’ll show that the class of regular languages is closed under the star operation. This
problem will help you investigate this property.
(a) Let A = {w ∈ {0, 1}∗ | w ends with 1}. Give the state diagram of a 2-state NFA N recognizing
A.
(b) Give a simple description of the language A∗.
(c) Consider the following failed attempt to construct an NFA recognizing A∗: Add an ε transition
from every accept state of N to the start state, and make the start state an accept state. Draw
the state diagram of this NFA, and call it N ′.
(d) What is L(N ′)? Give an example of a string w such that w ∈ L(N ′), but w /∈ A∗.
(e) Give the state diagram of an NFA that does recognize A∗.
5. (a) Given languages A,B, define the language MIX(A,B) by
MIX(A,B) = {x1y1x2y2 . . . xnyn | n ≥ 0, xi ∈ A, yi ∈ B}.
Note that each xi, yi is a string. Show that the class of regular languages is closed under MIX.
Hint: You don’t need to construct an NFA recognizing MIX(A,B) if you can find a way to
express it in terms of other operations.
(b) Given a language A over alphabet Σ, define the language TAIL(A) = {y ∈ Σ∗ | xy ∈
A for some x ∈ Σ∗}. Show that the regular languages are closed under TAIL.
Bonus Problems
1. In this problem, you will show that in the worst case, the subset construction uses a number of
states that is optimal up to a factor of 2.
(a) For a natural number k, let Rk be the language over alphabet {0, 1} consisting of strings
w such that the kth symbol from the right of w is a 0. Show that Rk is recognized by an
NFA with k + 1 states.
(b) Show that every DFA recognizing Rk requires at least 2
k states.
2. A coNFA is like an NFA, except it accepts an input w if and only if every possible state it could
end up in when reading w is an accept state. (By contrast, an NFA accepts w iff there exists an
accept state it could end up in when reading w.) Show that the class of languages recognized
by coNFAs is exactly the regular languages.
2