Page 1-3 Unicode alphabet, cf 1-11
Page 1-4 italic "S" in definition
P1.1.8 boldface Hint
P1.1.8 in (b) there are ten sets, not nine
P1.1.10 missing }
Page 1-11 unicode again
Page 1-23 two bold Hints
Page 1-29 middle "each other" --> "one another"
P.1.4.10 missing closing paren in not(p <-> q
E1.5.9 missing opening paren to match double closing paren )) ->
P.1.5.6 "whose second letter is A": should be "whose second letter is a"
P1.5.7 union in example should be intersection
P1.5.8(b) add the word "disjoint" before first "subsets"
E1.6.6 "settings"
P1.6.2, 1.6.3, 1.6.4, 1.6.10 (twice) boldface Hint
P1.6.7 set B = {d, l, n, s}
Page 1-55 Font of "Modus Ponens"
E1.7.9 "sometiimes"
P1.7.3, 1.7.4 bold Hint
P1.7.9 either AND or OR works, go with the English text
E1.8.1 bold Hint
P1.8.7 second statement missing ")" at end
Page 1-68 end first paragraph: "to one another"
E1.10.2(b) Answer has (1 -> (1 \/ (1 <-> 1) ) = 1. Equivalence should be 0<->0
E 1.10.7 (c). Answer has B(c) <-> B(c) ∨ B(d). LHS should be: not B(c)
P1.10.8 (a) spelling “predicate”, "three" should be "3"
P2.1.9 end sentence with a period.
P2.1.10 colon after "\langle c, j\rangle" each time.
E2.3.3 "or set of tuples of strings"
P2.3.3 bold-face "Hint"
P2.3.6 double period at end
P.2.3.7 the last statement F(x) xor F(y) should be fully quantified with
forall x exists y like the others
P2.3.9 "Write quantiified" has a double i.
E2.4.2, 2.4.3: bold-faced "Hint"
Page 2-21: "zero or more a's"
E2.5.4 bold-faced "Hint"
E2.5.8 "that"
P2.5.1 "then A^* has infinitely many elements"
P2.5.5, P2.5.7, P2.5.8 bold-faced "Hint"
P2.5.10 Part (c) should ask "if w is any string of minimum
length in X, and z is any string if minimum length in Y, then w and z
have the same length"
E2.6.6 bold-faced "Hint"
E2.6.7 change Scout to Indy to avoid using "s" twice (also change Solutions)
E2.8.10 (b) "Give examples of polynomials p, q, and r such that R_{k,p} is a
function, R_{k,q} is not total, and R_{k,r} is not well-defined."
P2.6.5 bold-faced "Hint"
E2.8.5 bold-faced "Hint"
P2.8.5 typo "relfexive"
P2.8.7 delete "}"
P2.8.8 bold-faced "Hint"
Page 2-42 line 3 of 2.9.2, "our main topic"; line 4 period should be comma,
line 9 "and if"
Page 2-43 (3) ... that is not a surjection should be: that is not a bijection
Page 2-43 add \spadesuit at end of Theorem
Page 2-44 line 9 "And f must be onto..."
P2.9.9 bold-faced "Hint"
Page 2-49 line 8 "order that is not a total order."
Page 2-50 line 3 of second Proof: add period after "b = a"
P2.10.1 "there is"
P2.10.2, 2.10.6, 2.10.7, 2.10.9, 2.10.10 bold-faced "Hint"
P2.10.6 "liinear"
P.2.10.8, change formula to \forall x: \exists y: \forall z: P(x, z) \to P(z, y)
Page 2-58 line 1 change "which" to "that"
P2.11.7 (c) refers to 2.10.8, change to "Give an example of such a P that also
has the property from Problem 2.10.8."
add part (d) Prove that if P is a linear order, then P^S is an equivalence relation
add part (e) Can you find an example of a P that is not a linear order, where
P^S is an equivalence relation?
P2.11.8 (d) statement to prove is not true, replace with
(d) Prove that for any element a of X, if a is in any set of Y, there is a set S(a)
that is a subset of any set T such that a is in T
(e) Prove that E(a, b) is true if and only if either S(a) = S(b) or neither a nor
b is in any set of Y.
Page 3-4 line 2 of code "return false"
Page 3-6 line 8 of code "d*d > x"
Page 3-6: code has “\%” in place of “%”
Page 3-7 line 3 of Definition: close quotes
E3.1.10 "if it returns false on line 5"
P3.1.1, P3.1.8 bold-faced "Hint"
P3.1.8 Reference to “LNA of Excursion 1.2”, should be “1.3”.
P3.1.10 line 4: missing space
Page 3-18 footnote 20: "discussed in Section 15.11"
Page 3-18 end of text "300-digit number"
E3.3.8 bold-face "Hint"
E3.4.10 x <= n should be x <= 2^n
P3.3.4, P3.3.7 bold-face "Hint"
P3.3.7 add "with real-number coefficients" at the beginning
P3.3.8 missing comma in list
Page 3-24 add \spadesuit at end of first paragraph
E3.4.2, E3.4.5 bold-faced "Hint"
E3.4.4 "given any finite set S"
P3.4.1 bold-faced "Hint"
P3.4.3 "Exercise 3.4.8", change constructed number from k to z
(in three places)
E3.5.3, E3.5.4, bold-faced "Hint"
P3.5.6 {0,1,...,n-1}
P3.5.7 stray space in "relatively", braces on set of {p_i}
Page 3-36 end of first paragraph: "to one another"
E3.6.1 bold-faced "Hint"
E3.6.3 "divide the same natural by the same positive natural",
"properties of naturals"
E3.6.7 delete "and say that", comma after first "D(Y, Z)"
P3.6.3 bold-faced "Hint"
P3.6.6 part (c) -- norm of x+iy is x^2 + y^2, length is square root of norm
P3.6.9 \subset should be \subseteq
Page 3-44 exercise 3, bold-faced "Hint"
E3.8.9 "fail to be distributive"
P3.8.2, P3.8.6 bold-faced "Hint"
E3.9.10 "if any prime p"
P3.9.8 bold-faced "Hint"
Page 3-60 line 3 "original n to be prime will..."
E3.11.3 add "real-Java" before "method", bold-faced "Hint"
P11.3.3 last line "apply that method"
P4.1.9 second method in (b) should be "void push (thing x)"
Page 4-11: "will success" --> "will succeed"
Page 4-12: third and fifth bullets, bold-faced "Hint"
E4.3.3 bold-faced "Hint"
E4.3.8 include case of P(0)
E4.3.10 add "for some real number g"
Page 4-28, line after last equation, "Since \phi < 1,"
P4.6.7 missing closing paren in S(R(x, y)
at end, missing closing paren in S(Q(x, y)
P4.6.8 In part (b), second thing to prove is "R(zy, y) = 0"
In (c) the RHS of the last equation should be "Q(Q(zxy, y), x)".
Page 4-38, footnote 27: replace by "Though note that various code examples and
exercises throughout text have used the real Java String class."
Page 4-43 footnote 31: period of first sentence should be after ")"
Page 4-49, Figure 4.14, change graph to be directed, with edges away from b and x
Page 4-50, line 8 "In our example of a directed graph in Figure 4-14..."
Page 4-52 "strongly connected if it has a path from any node to any other node",
"undirected cycle to be a non-empty path from a node to itself that _never
reuses an edge_ -- such a path must have three or more edges"
Page 4-59 last paragraph "As we will show below in Problem 4.11.3, "
Page 4-63 last method move one "}" to end
E4.11.8 (b) "with T tetrominos"
P4.11.3 -- explicitly bar use of "Fibonacci is worst case" claim from the text.
P4.11.7 line 4 "every pair of them"
P4.11.8 in the second bullet, “3^ii” should be just “3^i”.
Chapter 4 Index: add "Paren language", page 4-43
Solution to E1.6.8 "is are" --> "are"
Solution to E1.7.10 line 21, delete stray "]"
Solution to E1.10.7 both (a) and (c) are missing a right paren at the end
Solution to E2.5.1: rewrite in set builder notation, e.g., "{a}Sigma^* = {w: w
begins with a}"
Solution to E2.5.7 "lambda"
Solution to E2.6.6 Case 2: delete stray second colon
Solution to E2.6.7 change Scout to Indy to match question, in fourth bullet of (b)
capitalize "Case"
Solution to E2.6.8 (b), close paren in last line
Solution to E2.8.7: line 1 "ff" --> "if"
Solution to E2.8.9 "the only possibility is that R is also empty"
Solution to E2.8.10 (b): close paren in line 3, change second p(x) to q(x) and
third p(x) to r(x)
Solution to E2.9.4 (c) "f \circ f is the identity function"
Solution to E2.9.7 close paren in line 3
Solution to E2.10.6 line 3 of second bullet, delete stray ";", line 1 of
third bullet, close paren
Solution to E2.11.1, make sentences
Solution to E2.11.3, add "and"
Solution to E2.11.5 line 5, change period to comma
Solution to E2.11.6 (a) "any letter occurring in u"
Solution to E3.1.7: "2^n - 1", not "2 * n - 1"
Solution to E3.3.4: "there exist integers"
Solution to E3.3.8 (c): line 3, comma should be period
Solution to E3.4.8 line 4, "and verify"
Solution to E3.5.7 "him" --> "them"
Solutions to E3.6.9 and E3.6.10 are called "3.8.9" and "3.8.10"
Solution to E3.6.9 line 2 "and is thus composite", line 3 "2\times (t-1)"
Solution to E3.9.1: line 2 "greater than 1", line 4 "Z_r^*", line 6, add "and
b must be in Z_r^* since it has an inverse itself"
Solution to E3.9.8: line 7, "g^i is a generator", line 8 "g^i does not generate"
Solution to E3.9.9: line 4 "m \not= a"
Solution to E3.11.7 (b): Add second sentence "In the 1960's, American prisoners in Vietnam
communicated with one another using a "tap code", using a Polybius square
to convert letters into sequences of one to five taps on a wall or pipe."
Solution to E4.1.10: replace "[" by ";"
Solution to E4.3.9: line 4 "=" --> "+"
Solution to E4.3.10 line 5 close paren
Solution to E4.4.2 line 2: "2^{10}", next to last line "2^n + 2^n"
Solution to E4.4.6: line 1 "the statement that the"
Solution to E4.4.9: line 2 "that the product of any", line 5 "made in the end"
Solution to E4.6.1: line 2, equation ends "= x", not "= 0"
Solution to E4.6.2: line 2, {\tt times}
Solution to E4.6.3: line 1, P(y) should be "(x+y) - y = x"
Solution to E4.6.4: line 4, "or 0 if (x-y)-z = 0"
Solution to E4.6.5: line 1 spaces around "=", line 13 expression in \tt, close paren at
the very end
Solution to E4.7.10: delete "two l" at end
Solution to E4.9.8: line 2, "f(x) to f(y)", delete period
Solution to E4.9.9: line 3 delete one "four", line 5 "six graphs", not "six nodes".
Solution to E4.9.10: line 2 and line 3 close parens
Solution to E4.10.3 (a) "(((4*p)*p)*r)"
Solution to E4.10.6 close paren at end
Solution to E4.11.4 line 2 "passes"
Solution to E4.11.8 add "but not divisible by four.)" at end
Solution to E4.11.10 line 3 add comma after first "3", "It starts at 2 for j = 0,"
line 5 "so" --> "and thus"
P5.1.7: part (a) "by induction on n", part (b) delete the last “+”
Page 5-8: end of first paragraph, "is _in_" --> "_is_ in"
Page 5-9: line 3 after bullets, add "boolean operators"
P5.2.8: Add "\Sigma = \{a,b\}"
E5.4.3 bold-faced "Hint"
P5.4.6 "expressions" --> "languages"
P5.4.8 bold-faced "Hint"
E5.5.7 line 3, "gave a regular expression"
E5.5.9, E5.5.10: "method in pseudo-Java"
P5.5.3: bold-faced "Hint", "over regular expressions with alphabet {a}"
Page 5-28, footnote "Rules 1 through 4"
Page 5-29 exercise 2: bold-faced "Hint"
E5.7.1, E5.7.3, bold-faced "Hint"
P5.7.9 (a) "real axis"
Page 5-39 fourth bullet "are only" --> "at most"
Page 5-41 end of text "in Chapters 8 and 9."
E5.8.7 reference is to Exercise 5.8.6
P5.8.9 delete stray text after first "acyclic"
Page 5-46: line 2 of exercise 2, "define methods"
Page 5-47: end of second paragraph "or even calls to methods or
procedures", footnote 22 should end with a period
Page 5-48: four times "labelled" --> "labeled"
E5.10.4: reference is to Figure 5-10
P5.10.6: reference is to Figure 5-11
Page 9-2: periods after first and third bullets, line 2 of last paragraph of 9.1.1
Page 9-3 FIGURE 9-1 add (a), (b), (c), (d) under the four figures
Page 9-4: spacing of dash in line 3 of 9.1.3
Page 9-5 FIGURE 9-3 add captions "undirected graph", "with directions", and
"redrawn as rooted tree" under the three figures
E9.1.4: line 5, "to one another"
P9.1.3: eliminate extra (a), (b), (c), (d)
P9.1.7: Period at end of line 1
Page 9-11: move item 2 of list to the end
Page 9-12: line 5 of 9.3.1, "directory" --> "folder" twice
P9.3.9: add "(uses Java)", "write a real-Java method"
Page 9-23: line 2, "path from s_o to s", mark end of proof of Lemma 3
P9.4.9, line 3, font of "n"
Page 9-29: before table, add "(When we encounter nodes of out-degree 0 on the
stack, we can process more than one node at once.) Line 7 from bottom, "(3, 1)" -->
"(1, 3)", same change on following line
also in FIGURE 9-9, add edge from (2,0) to (3,0)
Page 9-31: eliminate period at end of first proof, line -3 of second proof "and
that neighbor must still"
P9.5.9: line 3, "n \times n board, where n is a perfect square,"
E9.6.2: reference is to Figure 9-12
E9.6.7: last line "stack" --> "open list"
E9.6.8: last full line "stack" --> "open list"
P9.6.4 (b) "on any non-root node"
P9.6.10: line 4, reference is to Figure 9-14
P9.6.10c "Show that in the graph of Figure 9-14, there exists a..."
Page 9-43 FIGURE: The dual graph in the book
is incorrect. Add an edge from the top left node to the node just
to the right of it.
Page 9-44: end of first paragraph, "in a directed graph"
Page 9-55: line 5 after end of proof, "on any optimal path"
P9.9.8 (c) line 2, "separated from Vernon"
E9.10.4: line 2, "with x_i sticks in the i'th pile"
E9.10.8: line 2, "picked up, and no one has yet won, then the game"
P9.10.6: line 5, "that paths exist"
P9.10.7 Correction: It is White’s move if the top node is OR,
and Black’s move if the top node is AND.
These are reversed in the problem statement.
P9.10.9: line 6, "in the upper right"
Replace part (a): A student claims that given any Boxes position,
they can determine who has the next move. The number of moves
made so far, they say, is the number of lines drawn on the board
minus the number of completed boxes. Is this correct?
Replace part (b): Give and justify an upper bound on the number
of possible positions in an a by b Boxes game.
Problem 9.10.10: Reverse the five examples in the problem statement,
so that in fact toads move left and frogs move right as it says.
Replace part (b) with FFxxTT, and part (c) with FFFxxxTTT.
Page 9-69 DIAGRAM The W's in the third board should be in the same place as
in the second board. In line 2 of exercise 1, bold-faced "Hint".
Page 14-3 Add fourth bullet: "A language L is defined to be {\bf recognizable}
if there exists a DFA that decides it. (We will later show that the
regular and recognizable languages are the same, but until we have done
that we will be careful to distinguish the two concepts.)"
P14.1.4 and P14.1.7: bold-faced "Hint"
P14.1.9 The first word “that” should be “the”.
P14.2.9: Add a period after last footnote.
P14.2.10 (5) Both words “regular” should be replaced by “recognizable”.
Also add "{\bf Hint:} See Problems 14.1.3 and 14.1.4."
Page 14-17, end of section 14.3.1, "there are" --> "then there are" twice
P14.3.9: "such that there exists some positive natural q such that for any..."
P14.3.10: "such that L \not= \emptyset,"
P14.5.1: "how to build an ordinary NFA..."
P14.5.2: bold-faced "Hint"
P14.5.4: "Let N be an ordinary NFA..."
P14.5.6: "closed under prefix if for every pair of strings u and v in \Sigma^*,
uv \in L implies u \in L."
P14.5.10: "language of some ordinary NFA with a single final state, that is not
the start state, if and only if \lambda \not\in S.", add right paren at end.
Page 14-36: last line of last full paragraph, change comma to colon.
P14.6.5: "Does there exist any two-state (ordinary) NFA, with input alphabet
\Sigma = {a, b}, that has a language whose..."
P14.6.7: Add condition to (b) that we never have states p, q, and r and letter a
such that Delta(p, a, r), Delta(q, a, r), and p \not= q. Replace (c) by "Given
the condition of part (b), prove that as we read any word w, the size of the
set delta^*(\iota, w) can never decrease."
P14.6.8: line 4, move * to superscript
P14.6.9: In part (b), delete the word “in”. In part (c), add "Let \Sigma = {a, b}."
Page 14-43: In item 2 of list, fix spacing of "i.e.".
Page 14-45 FIGURE 14-25: add a-loop on state q.
Page 14-47 end of last paragraph before Proof of Lemma: add "or one of the search
algorithms from Chapter 9."
P14.7.6: line 1, change "o" to "p" in first transition
P14.7.10: "oceans" should be \tt font rather than \it.
Page 14-54: line 5, "be a copy" --> "contain a copy". At end of second paragraph, add
"An electrical engineer might call this a {\bf parallel connection} of the two machines."
Page 14-55: just before new bullet, add "An electrical engineer might call this a
{\bf series connection} of the two machines." Second sentence of bullet, "A natural
way to proceed is to add two new states..."
Page 14-56: line 3 of footnote, italicize "e.g."
E14.8.9: reference should be to Exercise 14.8.4.
P14.8.3: "with exactly one final state (that is not the start state),"
P14.8.8: "given regular expression", in (b), "tester of Exercise 5.5.8"
P14.8.10: At end of (b), add "({\bf Hint: You may quote the results of Problems
14.1.3 and 14.1.4.)". In line 2 of part (c), "equivalent"
Page 14-65: third line from end, "loop on bb at state 2".
Page 14-66 FIGURE: In the right diagram of Figure 14-44, the circles on states
2 and 3 are single, not double.
Page 14-68, footnote: Replace with "We wound up with the same regular expression that
we are about to derive here, but the method we used there was specific to the
particular language. Of course, the suggestions given there about how to solve
the problem were influenced off-line by the general construction."
P14.10.2: Add "Before making the ordinary NFA, simplify the lambda-NFA to an
equivalent one with six states, using loops for the a^* components."
P14.10.4: "Paren from Problem 4.7.7. and Section 14.2."
P14.10.6: last line, "for any state r other than q,"
P14.10.10: In (a), "the set Lw^{-1}". In (c) "Argue that if D is an DFA
for L, and M is {\it any language at all}, then there exists a DFA D' for
LM^{-1}, such that D' can be obtained from D by simply changing the final state set."
Page 14-73: third line of third paragraph, delete period after "r.e.-NFA".
Page 14-74: line 6, "only final state 1, and transitions..."
Page 14-76: add "parallel connection, 14-54" to index.
Page 14-77: add "series connection, 14-55" to index.
Page 15-3: second bullet: "containing their input", third bullet "for their state".
Page 15-3-4, footnote 3: after "it is on", replace with "In Problem 15.1.7 you will
determine the possible number of {\bf configurations} that a 2WDFA with k states
and n input letters might have. If the 2WDFA runs for more than this number of
steps, it must at some point repeat a configuration. What happens after that?"
Page 15-7: (There is a major notational change that affects this entire proof. We
will now define k+1 functions from \Sigma^* to S\cup{d}, the first called f_0
and the others f_q for every state q in S. For any string w we will look at the
tuple of values of these k+1 functions.)
In line 1, "if M has k states q_1,...,q_k, with start state q_1,"
First bullet: "start M in state q_1", "and if so, in what state", "We define
f_0(w) to be that state if it exists, or f_0(w) = d if it doesn't" "So f_0(w)
is an element of the set S\cup {d}, where S is the state set of M and d is not
an element of S".
Second bullet, line 3 "in some state q_i", line 4 "we call this state f_i(w)",
line 5 "we define f_i(w) to be d. (In particular, f_i(\lambda) = d for all i.)
So each f_i is a function with domain \Sigma^* and range S\cup {d}".
New paragraph: "If we know f_0(w), f_1(w),...,f_k(w) for some string w, and x is
any string", "leaves w to the right in state f_0(w)" [We also change p_w to f_0(w)
and f_w(q) to f_i(w) in all the footnotes on this page.] Line 3 of
paragraph: "to the left in state q_i".
Line 4 of paragraph: "returns in state f_i(w)"
Lemma: "such that f_0(u) = f_0(v) and for all i, f_i(u) = f_i(v). Let x be..."
Line 4 of Proof: f_0(w) \not= d
Next paragraph: line 2 "in state q_i", line 4 "started in q_i", "in some state q_j",
line 5 "in state q_j", "if f_j(u) = f_j(v) = d", line 6 "f_j(u) = f_j(v)"
Page 15-8: First full paragraph: "So if f_0(u) = f_0(v) and f_i(u) = f_i(v) for all i"
line 3 "the number of possible tuples \langle f_0(u), f_1(u),..., f_k(u)\rangle,
where each member of the tuple is an element of S\cup{d}. There are (k+1)^{k+1}
possible tuples of this kind, so there are at most (k+1)^{k+1} possible
equivalence classes".
Next paragraph: "If we know \langle f_0(w),...,f_k(w)\rangle and M,"
"we can determine \langle f_0(wa),..., f_k(wa)\rangle"
"for all possible \langle f_0(w),..., f_k(w)\rangle and a", "renaming \iota
as q_1 and p as q_2"
Next paragraph: "possible values of \langle f_0(w),..., f_k(w)\rangle"
Delete sentence starting "A good notation".
First bullet "\langle q_1,d,d\rangle"
Rest of bullets: \iota --> q_1, p_w --> f_0(w), f_w(\iota) --> f_1(w),
f_w(p) --> f_2(w), p --> q_2
Page 15-9 FIGURE 15-4: Labels of states become q_1dd, q_2q_2q_1, ddq_1, q_1q_1q_1,
and q_1q_2q_1.
E15.1.1: "Find the state f_3(aabbab)."
E15.1.9: Delete parens around all the pairs in angle brackets.
P15.1.3: "possible tuples \langle f_0(u),..., f_k(u)\rangle"
P15.1.4 (a) "no ordinary DFA with fewer than"
P15.1.5: Notation changes throughout, starting in line 2 of (b). "let F_0(u)
be the following subset of S\cup {d}." q --> q_i, P_u --> F_0(u),
\iota --> q_1, "for any state q_i, F_i(u) is the subset of S\cup{d}"
"the condition \langle F_0(u),..., F_k(u)\rangle = \langle F_0(v),..., F_k(v)\rangle"
P15.1.6: "which tuples \langle f_0(u),..., f_k(u)\rangle"
"the values f_1(u) and f_2(u)", "as triples \langle f_0(u), f_3(u), f_4(u)"
P15.1.7: Add "Your function need not be the smallest possible function."
Page 15-16: third line from bottom, "we get context-free grammars"
Page 15-17: Figure 15-7 caption, "The r.e.-NFA made"
E15.2.4: delete first word "grammar"
Page 15-22: after first group of bullets, "Paren from Problem 4.7.7, Section 6.10, and
Section 14.2, and in fact..."
Page 15-24, line 9: "affect one another"
Page 15-27: last line, add period after "L(G)"
P15.5.3: "(2) for all naturals i,"
P15.3.9: end, reference is to P15.3.8
Page 15-31, third bullet: "equal to one another"
Page 15-34, second paragraph: "PDA can recognize a language", "with a means of {\it
recognizing} them"
E15.5.3: "given at the beginning of this section"
P15.5.9 (b) \subset should be \subseteq
Page 15-42, end: (see Section 15.11), we have shown the former problem to
be "NLOGSPACE-hard"
Page 15-44, footnote 41: the form "prove that a Turing machine...
Page 15-45: line 2, "There is one additional"
Page 15-47: line 2 after bullets, "Figure 15-14", line 4 of 15.6.4, "feasibility"
E15.6.6: delete last sentence
P15.6.2" "tape contents \Box w \Box w"
P15.6.9: "single natural uv (the product of u and v) in binary"
Page 15-51: line 7 from bottom, "(abc)^*. that is, a string of the form"
Page 15-56 FIGURE 15-17: Box on left says: SAY "YES"
Page 15-57: line 1 of Proof, "to one another", line 3, "the TD/TR Theorem above"
E15.8.4: bold-faced "Hint"
P15.8.1: line 4, "occurs at least once as s_i"
P15.8.7: Add before last sentence "(Note that if n < |w|, M will only ever see part
of w.)"
P15.8.10: Add at beginning "Let N be a halting NDTM."
Page 15-67: line 2, "to one another", line 3 of paragraph 4, "Figure 15-20", next
paragraph, references are to Figures 15-21a through 15-21d
Page 15-69: three times, reformat "L_{life}", footnote 75, "of the second edition"
E15.10.6: reformat "L_{life}"
P15.10.6: add "}" at end of first sentence
P15.10.10: "arithmetic hierarchy" should be \bf, not \it
Page 15-73, first line of second full paragraph, "polynomial time"
Page 15-74, footnote 85: "it has become one of the most"
Page 15-76, footnote 89: "of one another's work"
Page 15-77: line 4, "from Chapters 4, 8, and 9 that if", lines 5-6, "We saw several
ways" "Warshall's Algorithm, depth-first search, and breadth-first search", last
line, "differing only in the write operations and head moves" Footnote 91, after
first sentence, "DFS and BFS are also polynomial-time algorithms."
E15.11.1: bold-faced "Hint"
P15.11.1: line 5, "for a homework problem in this book", line 7, bold-faced "Hint"
P15.11.9: line 5, "all the cities"
Page 15-83: add to Index "arithmetic hierarchy, 15-71"
Page 15-85: "word" is page 15-50, "zero-knowledge proof" is 15-80
Solution to E5.1.1: "v \in \emptyset"
Solution to E5.4.6: line 3 of second paragraph, "\subseteq"
Solution to E5.10.2: reference is to Figure S-14
Solution to E5.10.3: reference is to Figure S-15
Solution to E5.10.6: reference is to Figure S-16
Solution to E5.10.8: reference is to Figure S-17
Solution to E5.11.7: line 5, add ")" before period
Solution to E5.11.8: line 1 "except that it has",
line 2 "declarations, so it begins with", line 4, double quotes in \tt font
Solution to E5.11.9: second paragraph, close paren in line 2
Solution to E9.1.9: line graph is <4, 4, 3, 3, 2>, other two
graphs are <4, 4, 4, 4, 3, 3, 2>.
Solution to E9.3.5: line 5, "as one another"
Solution to E9.3.9: line 3 from end, "the method is in the place"
Solution to E9.5.3: last line "and 1 as the start node."
Solution to E9.5.6: Delete "in the" at end
Solution to E9.5.7: "for each path starting at one of s' neighbors"
Solution to E9.6.6: should begin "Node y could be"
Solution to E9.9.1: line 2, "and goal node t"
Solution to E9.10.6: line 6, "knock down the middle pin"
Solution to E9.10.7: line 3, "For n = 4 White can only leave a single group"
Solution to E9.10.8: add at end "(We must verify that there are exactly eight ways for a
set of three cards to total 15, matching the eight ways to win Tic-Tac-Toe.)"
Solution to E14.1.1: line 5, "delta(delta^*(i, w), a) = delta(s, a)"
Solution to E14.1.5: "delta(i, 1) = i-1"
Solution to E14.1.7: last line, "five" --> "six" (corrected by hand currently)
Solution to E14.1.9: line 4, "that letter" --> "the first letter"
Page S-99 FIGURE S-24: add ">" symbol to state 1
Solution to E14.3.6: "We have state set"
Solution to E14.3.9: delete stray word "a"
Solution to E14.5.8: at very end, "Sigma^*bSigma^*", not "Sigma^*nSigma^*".
Solution to E14.6.5: line 2 "to a final state {q, r}", line 3 "to a final state
{p, q, r}".
Solution to E14.6.6: line 10, "thirteen states in the DFA", line 12 "splits into X"
Solution to E14.6.8: starting in line 2, add parens around "which means exactly
that Delta^*(iota, v, u) is true"
Solution to E14.6.9: "The set of states to be included in delta({p, q}, b) is the
union of the set of states with b-arrows form p and the set of states with
b-arrows from q."
Solution to E14.7.6: line 7, "has the transitive"
Solution to E14.7.9: next to last line, "By combining this move and lambda-moves,"
Page S-107, FIGURE S-32: in the left diagram, add a b-arrow straight from the
second-leftmost state to the second-rightmost state.
Solution to E14.8.7: line 1, "start state p, only final state r". Line 3,
"the improved lambda-NFA for the given..." Line 4, after set {1,...,9}, add
"start state 1, only final state 9. Line 5, fix right angle brackets -- four
are missing and one is reversed.
Page S-108: Caption to Figure S-33, "(b + aa^*bb)" as in handwritten correction.
Solution to E14.8.8: line 3 "state set", line 6 missing right angle bracket.
Solution to E14.8.10: line 5, delete extra comma
Solution to E14.10.6: line 3, replace second lambda with left angle bracket
Solution to E15.1.1: second paragraph, "f_3(aabbab)" twice, first and last lines
Solution to E15.1.6 (b): last line "2WDFA"
Solution to E15.1.8: line 3 delete "Start a", line 7 "sufficiently long"
Solution to E15.1.9 (b): "has a matching character"
Page S-115 FIGURE S-38: Caption on right is "R.E.-NFA WITHOUT STATES C AND Y"
Solution to E15.2.6: line 2, "Figure S-38", line 4 "eliminating states C and Y"
Solution to E15.3.7: line 6, "generated by the top A"
Solution to E15.5.4: end of first paragraph, add ")"
Solution to E15.5.5: eliminate space after "f"
Solution to E15.6.6: line 3, capital W in "While"
Solution to E15.8.10: "the TR languages"
Solution to E15.10.5, E15.10.6: Three places, reformat "L_{life}"
Solution to E15.11.4: "Section 14.3"