
The Theory of Computation  Bernard M.E. Moret 

ERRATA (Second Printing)
With many thanks to Jonathan Goldstine and Matthias Stallmann for
detailed and thoughtful comments on the third printing.

Chapter 2:
 p. 11, then throughout the text:
for didactic purposes, it would be preferable to have a fixed
definition for N, say not including 0, and a separate notation
for the version that does include 0, say N*.
 p. 18, second paragraph:
the functions f and g are defined to map natural integers to natural
integers for simplicity, but the definitions of asymptotic notation
extend naturally to larger domains, including real numbers.
 pp. 2122, definition of cycle, acyclic graph, and simple cycle:
Reorder the definitions to place the definition of simple path/simple
cycle before that of acyclic graphs and change the definition of
acyclic graph to be a graph without any simple cycles.
 p. 27, last line of Section 2.5:
the exponent should be x/2, not x
 p. 30, Exercise 2.4:
"natural" and "rational" should be switched.
 p. 32, first sentence:
the part starting with "for instance, ..." should be removed:
it is at best misleading, since that bijection of Exercise 2.4
is not between N and NxN and so cannot be a candidate for pairing.
 p. 37, Exercise 2.9:
clarification: the set is assumed to be finite.
 p. 39, Exercise 2.22:
The second sentence should be removed  as written, it sets a very
hard question. (It could be modified to ask whether 11 is the smallest
number for which Euler's formula will yield a quick answer, in which
case it becomes again an easy question.)
 p. 40, Exercise 2.31:
This exercise should be starred  it is a standard exercise in
combinatorics, but requires Stirling numbers of the second kind for
a concise expression or will have to be written as a complex sum
using inclusion/exclusion; deriving an upper bound is easy.

Chapter 3:
 p. 60, Definition 3.3:
there should be one more bullet, stating "If P is a regular expression,
so is (P)"
 p. 77, end of first paragraph:
just before "finally ...", add
"the start state of M is the pair of start states of M1 and M2"
 p. 78, end of first paragraph:
not an erratum, but a potentially confusing statement:
when stating "we do not yet know", the "we" denotes the student
or class, not the CS community  regular expressions are definitely
not closed under infinite union!
 p. 86, part 5 of Exercise 3.4, third line:
string 10111 should read 10101.
 p. 86, part 2 of Exercise 3.5:
needs clarification  the "except in the last four characters"
is ambiguous; any specific clarification will do.
 p. 87, automaton 2 of Exercise 3.7:
the upper righthand vertex has two arcs leaving it, both labelled 1;
the downward arc should be labelled 0.
 p. 90, Exercise 3.23:
clarification:
"the evaluation procedure defined in Exercise 3.12" should read
"the forward evaluation procedure defined in Exercise 3.12"
 p. 92, last line of Exercise 3.33:
"Conclude that the complement of SUB(L) is finite." should read
"Conclude that the complement of SUB(L) is regular."

Chapter 5:
 p. 129, Exercise 5.5:
the items should be numbered, not bulleted
 p. 136, last line (last line of Exercise 5.8):
"to the recursive functions" should read "to the primitive recursive functions"
 p. 140, line 19 (second line of the definition of b_to_u)
should read "b_to_u(x_) = double(b_to_u(x))"  that is, no use of
Succ in this case
 p. 148, first line below Definition 5.7:
the comma should be omitted
 p. 154, third line from the bottom (definition of theta(x,y)):
"step(x,x,y) > 0" should read "step(x,x,y) = 0"

Chapter 6:
 p. 212, proof of Theorem 6.7, definition of
F_{j}(I_{1},I_{2}):
the variables J and K should be quantified universally,
not existentially! This error makes nonsense out of Exercise 6.10 (same
page, see next erratum).
 p. 212, Exercise 6.10 should be removed entirely (see preceding erratum).
 p. 219, proof of Proposition 6.1, 5th and 6th lines
(not an error, but a potentially misleading statement):
"It then traverses each tree in postorder and records which prefixes of the guessed
string (if any) can be represented by each subtree."
In order to record such information accurately, much more than prefix information
must be stored along the way: a concatenation node, for instance, will require much
more general substring information. The intent was only to state that a postorder
traversal can be used, with suitable bookkeeping, to extract the prefix information.
 p. 221, Exercise 6.25, first line of second paragraph:
"recursive sets" should read "r.e. sets"

Chapter 7:
 p. 245, second line from the bottom:
the running time is O(nN), not just O(nN^{2}),
because the dynamic program, in order to fill a cell in the table of
O(nN) values, need only compute the minimum of two table values.
(See also Chapter 8, p. 302.)
 p. 282, Exercise 7.50, line 2:
"Delta_{2}" should read "Sigma_{2}"
 p. 282, Exercise 7.50, line 3:
"regular expression" should read "regular expressions"

Chapter 8:
 p. 302, second line after the equation:
the running time is O(nN), not just O(nN^{2}),
because the dynamic program, in order to fill a cell in the table of
O(nN) values, need only compute the minimum of two table values.
(See also Chapter 7, p. 245.) Similarly, the last line of the second
paragraph should read "in linear time" instead of "in quadratic time".
 p. 318, third line above Theorem 8.16:
missing a space between "PTAS" and the following parenthesis
 p. 341, Figure 8.11:
R and coR should be RP and coRP, respectively.
 p. 341, eighth line of first paragraph:
"p_{a} + 2^{p(x)} > 1/2" should be
"p_{a} + 2^{p(x)} exceeds 1/2".
 p. 341, tenth line of first paragraph:
"so that p_{a} = 1/2  2^{p(x)1}" should be
"so that we have p_{a} = 1/2  2^{p(x)1}".
 p. 342, eleventh line of first part of proof:
"such that r(n)+r'(n)=q(n)" should be
"such that we have r(n)+r'(n)=q(n)".
 p. 350, Exercise 8.25, third line from end of exercise:
there should be a space between the period and the hint.

Chapter 9:
 p. 389, third line before Exercise 9.9:
"less ambitious results" should be
"less ambitious result"

Index:

Under "Clique" there should be a reference to
pp. 333334.
Additional errata for the first printing can be found here.