Introduction to Automata Theory, Languages, and Computation: Errata For the First Printing Only

p. 1, l. 5 of second paragraph: "begun" -> "began" (Thanks to A. P. Marathe).

p. 14, l. 22, 24: Union and intersection are interchanged on the right sides (only) of these two equations. That is, the right sides should be (R union S) intersect (R union T) (Thanks to Shigeko Seki).

p. 28, l. 2: S(n) should be S_2(n). Much worse, on and off are completely and uniformly interchanged in items (1) and (2) at the top of p. 28. Alternatively, regard (1) and (2) as the proof for S_2 and (3) and (4) as the proof for S_1. However, there is then a missing detail in (2): you have to observe that as n+1 > 0, being in off after n+1 moves could not be explained by n+1=0 and you are just starting the automaton; that is, you must have been in state on after n moves (Thanks to Shigeko Seki).

p. 71, Fig. 2.17: State 1 is the start state (Thanks to Shigeko Seki).

p. 73, l. -16: "but none of the digits or decimal point" -> "and perhaps some digits, but not the decimal point" (Thanks to Shigeko Seki).

p. 77, l. -12, -11: ""the only accessible states of D are the" -> "all accessible states of D are." Also, delete "those" from l. -11 (Thanks to Shigeko Seki).

p. 77, l. -9, -8: "transitions" -> "transition" on l. -9, and "lead" -> "leads" on l. -8.

p. 79, l. -2: "we" should be capitalized (Thanks to EC).

p. 85, l. 9: right parenthesis missing at end.

p. 87, l -14: "we" -> "be" (Thanks to Yiheng Yang).

p. 100, l. 7: L(phi) should be L(phi*) (Thanks to Todd Smith).

p. 117, l. -10: closing quotes needed after +epsilon (Thanks to EC).

p. 131, l. 4: Closing quotes missing at end of sentence.

p. 136, Fig. 4.4(c): Missing arrowhead for Start (Thanks to Dave Maier).

p. 136, last line and p. 137, first line: state qr means we have seen only 0's, while ps means we have seen only 1's (Thanks to Jody DeRidder).

p. 138, l. 5: the first a should be a (Thanks to Dave Maier).

p. 138, l. 13: right parenthesis missing after L(E_2 (Thanks to Sunghow Wu).

p. 138, l. 18: (L(E_1,E_2))^R; i.e., } replaced by ) (Thanks to Sunghow Wu).

p. 138, l. -10, -7: Big left parenthesis missing after L and before E_1^R (Thanks to Dave Maier).

p. 142, l. 2: (2) tells us $w$ ends in a (not b) (Thanks to Todd Smith).

p. 142, l. 7: Closing quotes missing at end of sentence (Thanks to Dave Maier).

p. 146, Exercise 4.2.5(d): Find the derivatives with respect to 0 and 1 (Thanks to Dave Maier).

p. 159, bottom: Before partitioning the states as described, we need to eliminate any state that is not reachable from the start state (Thanks to Lenore Blum).

p. 161, l. -14: "nonexcepting" -> "nonaccepting" (Thanks to Jody DeRidder).

p. 176, l -2 of the box: delete "the" (Thanks to EC).

p. 177, l. 15: "w in T" should be "w in T*" (Thanks to Dave Maier).

p. 180, Exer. 5.1.3, l. 2: Delete "a" (Thanks to Tom Whaley).

p. 190, l. 16, 17: The ", and" at the end of item (b) belongs at the end of item (a) (Thanks to Dave Maier).

p. 191, Exercise 5.2.3: We have to add the condition that w is not epsilon (Thanks to Daehyun Yoon).

p. 192, l. 18: "sequences" -> "sequence" (Thanks to Dave Maier).

p. 195, l. -11: "we" -> "We" (Thanks to Dave Maier).

p. 199, l. 19, p. 200, many times in Fig. 5.14, and p. 205, three times in Fig. 5.16: There is no \ in #PCDATA (Thanks to Dave Maier).

p. 202, l. 14: Space between Disk and Disks is needed (Thanks to Dave Maier).

p. 205, Fig. 5.16: A declaration of !ELEMENT PROF (#PCDATA) is missing (Thanks to Tom Royce).

p. 208, l. -4 of box: Comma after "Fig" should be a period (Thanks to Dave Maier).

p. 210, l. -17: "An string" -> "Any string" (Thanks to Tom Whaley).

p. 210, l. -10: "an expression" -> "expressions" (Thanks to Dave Maier).

p. 214, Exercise 5.4.1, l. 2: remove first vertical bar (Thanks to Tom Whaley).

p. 219, l. 6: "and epsilon-NFA" -> "an epsilon-NFA" (Thanks to Tom Whaley).

p. 220, l. 1: "first-in-first-out" -> "last-in-first-out" (Thanks to Brian Andresen).

p. 244, l. 10: r_k -> k (Thanks to J\"org Bredno).

p. 250, l. -8: L'=M(P') -> L'=N(P') (Thanks to J\"org Bredno).

p. 268, first line of Fig. 7.3: The first body for E should be EC_1, not EC_3 (Thanks to Zeph Grunschlag).

p. 272, Exercise 7.1.10: "for every CFL without epsilon" was intended. Otherwise, the problem is trivial.

p. 276, l. 13 below figure: "and almost proved" -> "and we have almost proved" (Thanks to EC).

p. 280, l. 9: "uvw" -> "uwy.

p. 280, l. 12: "vwy" -> "vwx" (Thanks to Raj D. Kumar).

p. 281, Exercise 7.2.4, l. 1: missing right parenthesis after "Exercise 7.2.3" (Thanks to EC).

p. 281, Exercise 7.2.4: The hint is bad. Actually, you need to make the two middle blocks distinguished.

p. 307, l. 6: "constrainted" -> "constrained" (Thanks to Tom Whaley).

p. 333, l. -4: The TM starts with 0^m10^n1 on its tape (Thanks to Tom Whaley).

p. 342, l. -10: q-2 should be q_2.

p. 365, l. 17: The topic should read Simulating a Turing Machine by a real computer (Thanks to Mandayam Srinivas).

p. 382, Exercise 9.2.5: The L on the left of the displayed equation should be L', and the same change should be made in line 4 of the exercise.

p. 383, l. 17. P_2 and P_1 interchanged in the last sentence (Thanks to J\"org Bredno).

p. 391, l. 19: It is sufficient to consider the first m transitions.

p. 414, l. 5: "incontrovertable" -> "incontrovertible" (Thanks to A. P. Marathe).

p. 416, l. 5: delete "its" (Thanks to A. P. Marathe).

p. 416, l. -5: "edges" -> "edge" (Thanks to A. P. Marathe).

p. 417, l. 5: delete "of" (Thanks to A. P. Marathe).

p. 422, Theorem 10.4: We require that L_2 is in NP, among the hypotheses (Thanks to Prasad Tadepalli).

p. 424, l. 16-17: "Cook completeness" requires a hyphen (Thanks to A. P. Marathe and Dean Starrett).

p. 446, l. 1: The correct way to guarantee E is true is to make y_1,...y_{j-2} true and y_{j-1},...y_{m-3} false (Thanks to Prasad Tadepalli).

p. 447, l. -14: Hyphen missing in "NP complete" (Thanks to Kang-Rae Lee).

p. 451, l. -9: Capital needed in "for" (Thanks to Kang-Rae Lee).

p. 452, first line below box: "involve" -> "involves" (Thanks to Kang-Rae Lee).

p. 453, l. 9: Capital needed for "if" (Thanks to Kang-Rae Lee).

p. 453, l. 21: delete "of" (Thanks to Kang-Rae Lee).

p. 460, l. 12: v_0 should be v^{(0)}, and similarly for v_1 and v_2 (Thanks to Kang-Rae Lee).

p. 464, l. -9: "Exercise 10.4.4(c)" -> "Exercise 10.4.4(b)" (Thanks to Kang-Rae Lee).

p. 466, l. 4: n_i_1 -> n_{i+1} (Thanks to Kang-Rae Lee).

p. 466, l. 9: "in" -> "is" (Thanks to Kang-Rae Lee).

p. 468, ref. 6: the date, 1972, is missing (Thanks to A. P. Marathe).