CS 332: Theory of Computation Prof. Mark Bun
Boston University September 8, 2021
Homework 1 – Due Tuesday, September 14, 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 one bonus problem. Problems 1-4 and 6 are to be
turned in via Gradescope. Problem 5 will be autograded using AutomataTutor.
1. For each of the following languages, (i) give a plain English description of the language, and (ii)
give two examples of strings in the language and two examples of strings that are in Σ∗ but are
outside the language.
(a) L1 = {0x1 | x ∈ {0, 1}∗}
(b) L2 = {w ∈ {a, b}∗ | |w| ≥ 4} ∩ {xabbay | x, y ∈ {a, b}∗}
2. For each of the following languages, (i) describe the language using set-builder notation and
union/intersection/complement/reverse/concatenation operations (the notation used in Problem 1),
and (ii) give two examples of strings in the language and two examples of strings that are in Σ∗
but are outside the language.
(a) L3 = the set of all strings over alphabet {a, b, c} that are palindromes (read the same forwards
and backwards) or start with a. (For example, bacab and cabbac are palindromes.)
(b) L4 = the set of all strings over alphabet {1, 2, . . . , 9} whose length is divisible by a, where a
is the first symbol of the string.
3. Which of the following statements are true or false, for all alphabets Σ? For each, provide either a
proof or a counterexample.
(a) For all strings x, y, z ∈ Σ∗, we have |xR ◦ ε ◦ zy| = |x| + |y| + |z|. (Recall that ◦ denotes
concatenation.)
(b) For all languages L1, L2 ⊆ Σ∗, we have (L1 ∩ L2)R = LR1 ∩ L
R
2 .
(c) For all languages L ⊆ Σ∗, we have L ◦ L = {ww | w ∈ L}.
(d) For all languages L1, L2, L3 ⊆ Σ∗, we have L1 ◦ (L2 ∪ L3) = (L1 ◦ L2) ∪ (L1 ◦ L3).
4. Consider the following state diagram of a DFA M using alphabet Σ = {A,B}.
1
q0start
q1 q2
q3 q4
A
B
A
A
B
B
A
B
B
A
(a) What is the start state of M?
(b) What is the set of accept states of M?
(c) Give a formal description of the machine M (i.e., as a 5-tuple).
(d) What sequence of states does the machine go through on input ABBAB?
(e) Does the machine accept the string ABBAA?
(f) Give a simple description of language recognized by M . (Either plain English or set-builder
notation is fine.)
5. This problem will be autograded using AutomataTutor. Visit http://automatatutor.com/ and
click on “Sign Up.” Make an account using your name and @bu.edu email address (it is important
for recording grades that the information for your account match the information on the course list
provided by the university). We’ll provide more specific information about how to register for this
course on Piazza.
Give state diagrams of DFAs with as few states as you can recognizing the following languages.
You may assume that the alphabet in each case is Σ = {0, 1}.
(a) L1 = {w | w contains the substring 100}.
(b) L2 = {w | w is any string except for 1001}.
(c) L3 = {w | every even position of w is 0}.
Give state diagrams of NFAs with as few states as you can recognizing the following languages.
You may assume that the alphabet in each case is Σ = {0, 1}.
(d) L4 = {w | w ends with an odd number of 0’s}.
(e) L5 = {w | the length of w is divisible by either 2 or 3}.
6. Draw (and include in the PDF you submit to Gradescope) state diagrams of DFAs with as few
states as you can recognizing the following languages. You may assume that the alphabet in each
case is Σ = {0, 1}.
2
http://automatatutor.com/
@bu.edu
(a) L6 = {w | w is a string of the form x1y1x2y2 . . . xnyn for some natural number n such that
if x is the integer with binary representation x1x2 . . . xn and if y is the integer with binary
representation y1y2 . . . yn, then x < y}. Both x and y are presented starting with the most
significant bit and may have leading 0s.
(b) L7 = {w | w represents a binary number that is divisible by 4}. The number is presented
starting from the most significant bit and can have leading 0s.
Bonus Problem
(a) Show that for any natural number n, the language PADn = {w ∈ {0, 1}∗ | w ends with
n copies of 0} is regular.
(b) Give a state diagram of a DFA recognizing the language ADD = {w | w is a string of the form
x1y1z1x2y2z2 . . . xnynzn for some n ≥ 0 such that x + y = z as binary numbers}. Here, x, y, z
are presented starting from the least significant bit and can have trailing 0’s. The empty string
represents the number 0.
3