Description
CMSC303 Introduction to Theory of Computation Assignment 1
1 Exercises
1. (6 marks) Sipser, Ex. 0.3: Let A be the set {x, y, z} and B be the set {x, y}.
(a) (1 mark) Is A a subset of B?
(b) (1 mark) Is B a subset of A?
(c) (1 mark) What is A ∪ B?
(d) (1 mark) What is A ∩ B?
(e) (1 mark) What is A × B?
(f) (1 mark) What is the power set of B?
2. (2 marks) Sipser, Ex. 0.4: If A has a elements and B has b elements, how many elements are in A×B? Explain
your answer.
3. (2 marks) Sipser, Ex. 0.5: If C is a set with c elements, how many elements are in the power set of C? Explain
your answer.
4. (7 marks) Sipser, Ex. 0.6: Let X be the set {1, 2, 3, 4, 5} and Y be the set {6, 7, 8, 9, 10}. The unary function
f : X 7→ Y and the binary function g : X × Y 7→ Y are described in the following tables.
n f(n)
1 6
2 7
3 6
4 7
5 6
g 6 7 8 9 10
1 10 10 10 10 10
2 7 8 9 10 6
3 7 7 8 8 9
4 9 8 7 6 10
5 6 6 6 6 6
(a) (1 mark) What is the value of f(2)?
(b) (2 marks) What are the domain and co-domain of f?
(c) (1 mark) What is the value of g(2, 10)?
(d) (2 marks) What are the domain and co-domain of g?
(e) (1 mark) What is the value of g(4, f(4))?
5. (3 marks) Sipser, Ex. 0.7: For each part, give a relation that satisfies the condition.
1
(a) (1 mark) Reflexive and symmetric but not transitive.
(b) (1 mark) Reflexive and transitive but not symmetric.
(c) (1 mark) Symmetric and transitive but not reflexive.
2 Problems
1. (2 marks) Sipser, Prob. 0.12 (0.11 in 2nd edition): Find the error in the following proof that all horses are the
same color.
CLAIM: In any set of h horses, all horses are the same color.
PROOF: By induction on h.
Base Case: For h = 1. In any set containing just one horse, all horses clearly are the same color.
Induction Step: For k ≥ 1 assume that the claim is true for h = k and prove that it is true for h = k + 1. Take
any set H of k + 1 horses. We show that all the horses in this set are the same color. Remove one horse from
this set to obtain the set H1 with just k horses. By the induction hypothesis, all the horses in H1 are the same
color. Now replace the removed horse and remove a different one to obtain the set H2. By the same argument, all
the horses in H2 are the same color. Therefore all horses in H must be the same color, and the proof is complete.
2. (4 marks) Prove using induction that
Xn
m=0
m =
n(n + 1)
2
.
2
CMSC303 Introduction to Theory of Computation Assignment 2
Unless otherwise noted, the alphabet for all questions below is assumed to be Σ = {0, 1}.
1. (6 marks) This question tests your comfort with “boundary cases” of DFA’s. Draw the state diagrams of DFA’s
recognizing each of the following languages.
(a) (2 marks) L = {} for the empty string.
(b) (2 marks) L = ∅.
(c) (2 marks) L = {0, 1}
∗
.
2. (8 marks) This question tests your ability to design DFAs and NFAs.
(a) (2 marks) Draw the state diagram for a DFA recognizing language L1 = {x | x contains at least two 1s}.
(b) (2 marks) Draw the state diagram for a DFA recognizing language L2 = {x | x contains at most one 0}.
(c) (4 marks) Draw the state diagram for a NFA recognizing language L3 = L1 ∪ L2.
3. (3 marks) In this question, you will study closure of regular languages under certain operations. Specifically,
show that if M is a DFA that recognizes language B, then swapping the accept and nonaccept states in M yields
a new DFA M0
recognizing the complement of B, B. Which operation does this imply the regular languages
are closed under?
4. (6 marks) This question tests your ability to prove a language is regular using the closure properties of regular
languages. Given languages A and B, define the operation · as
A · B := {x | x ∈ A and x does not contain any string in B as a substring.}.
Prove that the class of regular languages is closed under the · operation. (Hint: Recall that by DeMorgan’s law,
for any sets X and Y , one has X ∩ Y = ¬(¬X ∪ ¬Y ).)
5. (6 marks) This question tests your understanding of the equivalence between DFAs and NFAs. Consider NFA
M = ({q1, q2}, {0, 1}, δ, q1, {q1}) for δ defined as:
δ 0 1
q1 {q1, q2} {q2} ∅
q2 ∅ {q1} {q1}
Draw both the state diagrams for M and for a DFA M0
equivalent to M based on the construction of Theorem
1.39 in the text (recall the latter proves that DFAs and NFAs are equivalent).
6. (Bonus, 5 marks) This question demonstrates that although DFAs and NFAs are equivalent in terms of the sets of
languages they recognize, they are provably not equivalent in terms of efficiency (i.e. DFAs may require many
more states to recognize a language than an NFA). Consider the language Ck = Σ∗0Σk−1
for k ≥ 1.
Convince
yourself that an NFA with k + 1 states for recognizing Ck exists (no need to include this in your assignment
answer). Now, prove that for any k, Ck cannot be recognized by a DFA with less than 2
k
states.
1
CMSC 303 Introduction to Theory of Computing Assignment 3
1. [12 marks] This question develops your ability to devise regular expressions, given an explicit definition of a
language. For each of the following languages, prove they are regular by giving a regular expression which
describes them.
Justify your answers.
(a) L = {x | x begins with a 0 and ends with a 1}.
(b) L = {x | x contains at least four 0’s}.
(c) L = {1, 11, }.
(d) L = {x | the length of x is at most 3}.
(e) L = {x | x doesn’t contain the substring 110}.
(f) L = {x | |x| > 0, i.e. x is non-empty}.
2. [20 marks] This question tests your understanding of how to translate a regular expression into a finite automaton. Using the construction of Lemma 1.55, construct NFAs recognizing the languages described by the
following regular expressions.
(a) [5 marks] R = ∅
∗
.
(b) [15 marks] R = (0 ∪ 1)∗111(0 ∪ 1)∗
.
3. [15 marks] This question tests your understanding of how to translate a finite automaton into a regular expression. Consider DFA M = (Q, Σ, δ, q, F) such that Q = {q1, q2, q3}, q = q1, F = {q1, q3}, and δ is given
by:
δ 0 1
q1 q2 q2
q2 q2 q3
q3 q1 q2
Draw the state diagram for M, and then apply the construction of Lemma 1.60 to obtain a regular expression
describing L(M).
4. [15 marks] This question allows you to practice proving a language is non-regular via the Pumping Lemma.
Using the Pumping Lemma (Theorem 1.70), give formal proofs that the following languages are not regular:
(a) L =
www | w ∈ {0, 1}
∗
.
(b) L = {1
n0
m1
n | m, n ≥ 0}.
(c) L =
x | x ∈ {0, 1}
∗
is not a palindrome
.
Recall a palindrome is a string that looks the same forwards
and backwards. Examples of palindromes are “madam” and “racecar”.
1
5. [4 marks + 4 marks bonus] This question reveals important subtleties of the Pumping Lemma. Let B =
0
kx0
k
| k ≥ 1 and x ∈ Σ
∗
.
(a) [4 marks] Consider the following argument, which claims to prove that B is not regular.
Assume B2 is regular, and let p be the pumping length. Consider string s = 0p10p ∈ B2, and decompose
it as s = xyz with x = , y = 0p
, z = 10p
. Then, pumping s down by setting i = 0 yields string
s
0 = xyi
z = xy0
z = 10p 6∈ B2. Hence, by the Pumping Lemma, we have a contradiction. We conclude
that B2 is not regular.
The question is: What is wrong with this proof?
(b) [4 marks, bonus] Prove that, in fact, B is regular.
2
CS 303 Introduction to Theory of Computing Assignment 4
1. [12 marks] This question develops a basic understanding of CFGs and parse trees. Consider the grammar G
below.
E → E + T | T (1)
T → T × F | F (2)
F → (E) | 2 (3)
For each string below, give a parse tree of a derivation in G.
(a) 2
(b) 2 + 2 + 2
(c) ((2 + 2) × (2))
2. [10 marks] We have seen in class that the sets of both regular and context-free languages are closed under the
union, concatenation, and star operations. We have also seen in A2 that the regular languages are closed under
intersection and complement. In this question, you will investigate whether the latter also holds for context-free
languages.
(a) Use the languages A = {a
mb
nc
n | m, n ≥ 0} and B = {a
nb
nc
m | m, n ≥ 0} to show that the class
of context-free languages is not closed under intersection. You may use the fact that the language C =
{a
nb
nc
n | n ≥ 0} is not context-free.
(b) Using part (a) above, show now that the set of context-free languages is not closed under complement.
3. [15 marks] This question develops your ability to design CFGs. For each of the following languages, give a
CFG. Assume the alphabet is Σ = {0, 1}. For string x = x1x2 · · · xn, we define x
R := xn · · · x2x1, i.e. this
operation reverses the order of the symbols in x. Justify your answers briefly.
(a) {x | x starts and ends with the same symbol}.
(b) {x | the length of x is odd}.
(c)
x | x = x
R, that is, x is a palindrome
.
(d) ∅.
(e) For this part, set Σ = {a, b, $}. The language is then
x1$x2$ · · · $xk | k ≥ 1, each xi ∈ {a, b}
∗
, and for some i and j, xi = x
R
j
.
1
4. [15 marks] This question develops your ability to design PDAs. For parts (a), (b), (c), and (d) of question 3
above, give state diagrams of pushdown automata. For each automata, include a brief description of the idea
behind its design.
5. [10 marks] This question forces you to practice the generic construction for mapping a CFG to a PDA. Specifically, for the grammar G from question 1, use the construction from Theorem 2.20 to construct an equivalent
PDA P.
2
CMSC 303 Introduction to Theory of Computation Assignment 5
1. [6 marks] This question asks you to examine the formal definitions of a TM and related concepts closely. Based
on these definitions, answer the following.
(a) A configuration of a Turing Machine (TM) consists of three things. What are these three things?
(b) Can a Turing machine ever write the blank symbol t on its tape?
(c) Can the tape alphabet Γ be the same as the input alphabet Σ?
(d) Can a Turing machine’s head ever be in the same location in two successive steps?
(e) Can a TM contain just a single state?
(f) What is the difference between a decidable language and a Turing-recognizable language?
2. [8 marks] This question gets you to practice describing TM’s at a semi-low level. Give an implementation-level
description of a TM that decides the language
L = {x | x contains twice as many 0s as 1s}.
By implementation-level description, we mean a description similar to Example 3.11 in the text (i.e. describe
how the machine’s head would move around, whether the head might mark certain tape cells, etc. . . . Please do
not draw a full state diagram (for your sake and for ours)).
3. [9 marks] This question investigates a variant of our standard TM model from class. Our standard model
included a tape which was infinite in one direction only. Consider now a TM whose tape is infinite in both
directions (i.e. you can move left or right infinitely many spaces on the tape). We call this a TM with doubly
infinite tape.
(a) [3 marks] Show that a TM with doubly infinite tape can simulate a standard TM.
(b) [5 marks] Show that a standard TM can simulate a TM with doubly infinite tape.
(c) [1 mark] What does this imply about the sets of languages recognized by both models?
4. [10 marks] This question studies closure properties of the decidable and Turing-recognizable languages.
(a) [5 marks] Show that the set of decidable languages is closed under concatenation.
(b) [5 marks] Show that the set of Turing-recognizable languages is closed under concatenation. (Hint: This
is trickier than part (a) because if a (deterministic) Turing machine decides to split an input string x as
x = yz and check if y ∈ L1 and z ∈ L2, i.e. to check if x ∈ L1 ◦ L2, then running the recognizer for L1
on y (say) may result in an infinite loop if y 6∈ L1.)
1
5. [5 marks] This question allows you to explore variants of the computational models we’ve defined in class.
Let a k-PDA be a pushdown automaton that has k stacks. In this sense, a 0-PDA is an NFA and a 1-PDA
is a conventional PDA. We know that 1-PDAs are more powerful (recognize a larger class of languages) than
0-PDAs. Show that 2-PDAs are more powerful than 1-PDAs. (Hint: Recall from A4 that the language L =
{a
nb
nc
n | n ≥ 0} is not context-free.)
2
CMSC 303 Introduction to Theory of Computation Assignment 6
1. [10 marks] We begin with some mathematics regarding uncountability. Let N = {0, 1, 2, 3, . . .} denote the set
of natural numbers.
(a) [5 marks] Prove that the set of integers Z = {. . . , −3, −2, −1, 0, 1, 2, 3 . . .} has the same size as N by
giving a bijection between Z and N.
(b) [5 marks] Let B denote the set of all infinite sequences over {0, 1}. Show that B is uncountable using a
proof by diagonalization.
2. [9 marks] We next move to a warmup question regarding reductions.
(a) [2 marks] Intuitively, what does the notation A ≤ B mean for problems A and B?
(b) [2 marks] What is a mapping reduction A ≤m B from language A to language B? Give both a formal
definition, and a brief intuitive explanation in your own words.
(c) [2 marks] What is a computable function? Give both a formal definition, and a brief intuitive explanation
in your own words.
(d) [3 marks] Suppose A ≤m B for languages A and B. Please answer each of the following with a brief
explanation.
i. If B is decidable, is A decidable?
ii. If A is undecidable, is B undecidable?
iii. If B is undecidable, is A undecidable?
3. [40 marks] Prove using reductions that the following languages are undecidable.
(a) [8 marks] L = {hMi | M is a TM and L(M) = Σ∗}.
(b) [8 marks] L = {hMi | M is a TM and {000, 111} ⊆ L(M)}.
(c) [8 marks] L = {hMi | M is a TM which accepts all strings of even parity}. (Recall the parity of a string
x ∈ {0, 1} is the number of 1’s in x.)
(d) [8 marks] L =
hMi | M is a TM that accepts w
R whenever it accepts w
. Recall here that w
R is the
string w written in reverse, i.e. 011R = 110.
(e) [8 marks] Consider the problem of determining whether a TM M on an input w ever attempts to move its
head left when its head is on the left-most tape cell. Formulate this problem as a language and show that it
is undecidable.
1
CMSC 303 Introduction to Theory of Computation Assignment 7
Unless otherwise noted, the alphabet for all questions below is assumed to be Σ = {0, 1}. This assignment focuses on
the complexity classes P and NP, as well as polynomial-time reductions.
1. [12 marks]
(a) [4 marks] Let f(n) = 4n
2 − 30n + 6. Prove that f(n) ∈ O(n
2
). In your proof, give explicit values for c
and n0.
(b) [4 marks] Let f(n) = n
999 and g(n) = (√
log n)
√
log n. Precisely one of the following two claims is true:
f(n) ∈ O(g(n)), g(n) ∈ O(f(n)). Prove whichever one is true. In your proof, give explicit values for c
and n0. (Hint: Note that an arbitrary function f(n) can be rewritten as 2
log2
(f(n)).)
(c) [4 marks] This question tests an important subtlety in the definition of “polynomial-time”. One of the most
famous open problems in classical complexity theory is whether the problem of factoring a given integer
N into its prime factors is solvable in polynomial time on a classical computer1
. Given positive integer N
as input, why is the following naive approach to the factoring problem not polynomial-time?
1: Set m := 2.
2: Set S := ∅ for S a multi-set.
3: while m ≤ N do
4: if m divides N then
5: Set S ∪ {m}.
6: Set N = N/m.
7: else
8: Set m = m + 1.
9: end if
10: end while
11: Return the set S of divisors found.
2. [6 marks] Let co-NP denote the complement of NP. In other words, intuitively, co-NP is the class of languages
L for which if input x 6∈ L, then there is an efficiently verifiable proof of this fact, and if x ∈ L, then no proof
can cause the verifier to accept.
Prove that if P = NP, then NP is closed under complement, i.e. NP = co-NP. How can closure of NP under
complement hence potentially be used to resolve the P vs NP question?
3. [10 marks] In class, we introduced the language
CLIQUE = {hG, ki | G is a graph containing a clique of size at least k}.
1
In fact, many popular cryptosystems are based on the assumption that this problem is not efficiently solvable. Recall from class, however, that
in 1994 it was shown by Peter Shor that quantum computers can efficiently solve this problem!
1
Consider now two further languages:
INDEPENDENT-SET = {hG, ki | G is a graph containing an independent set of size at least k}
VERTEX-COVER = {hG, ki | G is a graph containing a vertex cover of size at most k}.
Here, for graph G = (V, E), an independent set S ⊆ V satisfies the property that for any pair of vertices
u, v ∈ S, (u, v) 6∈ E. A vertex cover S ⊆ V satisfies the property that for any edge (u, v) ∈ E, at least one of
u or v must be in S.
(a) [4 marks] Prove that CLIQUE ≤p INDEPENDENT-SET. (Hint: Given a graph G, think about its complement. Google “complement graph” for a definition.)
(b) [6 marks] Prove that INDEPENDENT-SET ≤p VERTEX-COVER.
4. [8 marks] Let CNFk = {hφi | φ is a satisfiable CNF-formula where each variable appears in at most k places}.
Show that CNF3 is NP-complete. (Hint: Suppose a variable x appears (say) twice. Replace the first and second
occurrences of x with new distinct variables y1 and y2, respectively. Next, add clauses to ensure that y1 = y2.
To do this in CNF form, recall that y1 = y2 is logically equivalent to (y1 =⇒ y2) ∧ (y2 =⇒ y1), and that
(a =⇒ b) can be rewritten as (a ∨ ¯b) ∧ (
¯b ∨ a). How can this trick be applied more generally when x appears
m > 2 times?)
5. [8 marks] It is possible for a problem to be NP-hard without actually being in NP itself. For example, the halting
problem from class is clearly not in NP, since it is undecidable. However, in this question, you will show that
the language HALT = {hM, xi | M is a TM which halts on input x} is NP-hard. Is the halting problem hence
NP-complete?
6. [8 marks] In class, we have focused on decision problems, i.e. deciding whether x ∈ L or not. For example,
given a 3-CNF formula φ, recall that the decision problem 3SAT asks whether φ is satisfiable or not. In practice,
however, we may not just want a YES or NO answer, but also an actual assignment which satisfies φ whenever
φ is satisfiable. It turns out that in certain settings, being able to solve the decision version of the problem (e.g.
3SAT) in polynomial time implies we can also solve the search version (e.g. find the satisfying assignment
itself) in polynomial time. Problems satisfying this property are called self-reducible.
Your task is as follows: Show that 3SAT is self-reducible. In other words, given any 3-CNF formula φ and a
polynomial-time black-box M for determining if φ is satisfiable, show how to find a satisfying assignment for
φ in polynomial time. You may assume that M is able to decide all CNF formulae with at most 3 variables per
clause.
2
CMSC 303 Introduction to Theory of Computation Course Mini-Project
For this reason, your mini-project will consist of the following task. First, please independently
read Sections 8.1 and 8.2 on Space Complexity. This will introduce you to the complexity class PSPACE and Savitch’s
theorem. Next, answer the following questions.
1. [2 marks] In words, which class of problems does PSPACE characterize?
2. [4 marks] Show that PSPACE is closed under the concatenation and star operations.
3. [4 marks] Prove that NP ⊆ PSPACE by giving a polynomial-space algorithm for simulating an NP machine
(use Theorem 7.20 for this, which says a language is in NP iff it is decided by a non-deterministic polynomial
time Turing machine).
4. [2 marks] Why is Savitch’s theorem surprising, given our study of P versus NP?
5. [14 marks] This question studies the proof of Savitch’s theorem. You may assume the TM M in the proof can
compute function f(n) in the proof in O(f(n)) space.
(a) [2 marks] In words, give a high-level overview of how the proof of Savitch’s theorem works.
(b) [6 marks] The CANYIELD procedure in the proof has 6 steps: Describe in a sentence or two the purpose
of each step.
(c) [2 marks] Why does the machine M in the proof correctly simulate the NTM N?
(d) [4 marks] Why does M use O(f
2
(n)) space?
1