CS 332: Theory of Computation Prof. Mark Bun
Boston University September 14, 2021
Homework 2 – Due Tuesday, September 21, 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 6 required problems and two bonus problems.
1. Consider the following state diagram of an NFA N over alphabet {A,B}.
q0start
q1 q2 q3
q4 q5
ε
ε
A
B
A
B
B
A
(a) Give a formal description of the machine N as a 5-tuple.
(b) Does the machine accept the string BBAA?
(c) Does the machine accept the string BBABBB?
(d) Does the machine accept the string BAAB?
(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
A
ε
B
B
A
B
B
(a) Consider running N on input AABB. 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. (NFAs can be simpler than DFAs) Consider the language L = {w ∈ {0, 1}∗ | w does not
contain both 0 and 1}.
(a) Give the state diagram of an NFA recognizing L that has exactly one accept state.
(b) Prove that every DFA recognizing L requires at least two accept states.
4. (Closure care) On Thursday, 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 contains the symbol 1}. Give the state diagram of a 2-state DFA D
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 D 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) For a string w ∈ {0, 1}∗, define the inversion INV(w) to be the string where 0’s in w are
replaced by 1’s and 1’s are replaced by 0’s. Given a language L ⊆ {0, 1}∗, define the language
INV(L) = {w | INV(w) ∈ L}. Show that the class of regular languages is closed under INV.
(b) Given languages A and B over the same alphabet Σ, define the language A \ B = {w ∈ Σ∗ |
w ∈ A but w /∈ B}. Show that the regular languages are closed under the operation “\”.
6. (Regex to description) Give plain English descriptions of the languages generated by each of the
following regular expressions
(a) b(ab)∗
(b) (0 ∪ 1)((0 ∪ 1)(0 ∪ 1)(0 ∪ 1))∗
(c) (a ∪ b)∗ ∪ (b ∪ c)∗
(d) ε∗
Bonus Problems
1. Given a language L over alphabet Σ, define the language cdr(L) = {y ∈ Σ∗ | ay ∈ L for some a ∈
Σ}. Show that the regular languages are closed under cdr.1
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.
1
https://www.gnu.org/software/emacs/manual/html_node/eintr/car-_0026-cdr.html
2
https://www.gnu.org/software/emacs/manual/html_node/eintr/car-_0026-cdr.html