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"