Introduction to Automata Theory, Languages, and Computation: Errata for the First, Second, and Third Printings

List of Errata for the First and Second Printings Only.

List of Errata for the First Printing Only.

In addition, the following were not corrected in time for the third printing, but were corrected for the fourth printing:

p. 18, l. 21: Capitalize "we" in "we must be careful..." (Thanks to Sebastian Hick).

p. 21, l. 4: "right" -> "left" (Thanks to Sebastian Hick).

p. 25, l. 17: The reference to Eq. (1.10) should be to Eq. (1.11) (Thanks to Sebastian Hick).

p. 35, l. 7: "by" -> "be" (Thanks to Sebastian Hick).

p. 42, Fig. 2.2(b): Period after "ship" should be a comma (Thanks to Sebastian Hick).

p. 79, l. 9: "epsilon-DFA" -> "epsilon-NFA" (Thanks to Sebastian Hick).

p. 85, l. -9: "is" before "the set..." (Thanks to Sebastian Hick).

p. 97, l. 1 of text: P_j -> P_i (Thanks to Sebastian Hick).

p. 118, l. 13: The w after "To see why, if" should be w_i (Thanks to Sebastian Hick).

p. 120, l. 4: "than" -> "then" (Thanks to Kirk Bulis).

p. 147, Exercise 4.2.7, l. 1: The last symbol for x should be b_n, not b_m (Thanks to Tapani Lindgren).

p. 196, l. 8: Delete "the" (Thanks to Ben Pfaff).

p. 216, l. 2: "Interion" -> "Interior" (Thanks to Cheryl Dugas).

p. 222, l. 4: "chose" -> "choose" (Thanks to Jennifer Johnson).

p. 233, 4 lines below Fig. 6.5: "than" -> "then" (Thanks to Yingge Wang).

p. 234, l. 11: eliminate one ",epsilon" in (r,epsilon,epsilon) (Thanks to Cheryl Dugas).

p. 276, l. -2: quotes should appear after 'game' rather than 'follows' (Thanks to Guray Alsac).

p. 290, Eq. (7.1): The term Gamma for the stack alphabet is missing (Thanks to Chittaranjan Tripathy).

p. 303, Exercise 7.4.5, l. 1: "so can" -> "to" (Thanks to Christian Lemburg).

p. 316 last line of box: "is" needed before first "undecidable" (Thanks to Christian Lemburg).

p. 321, l. 19: "repeatedly" -> "enters a loop in which it" (Thanks to Christian Lemburg).

p. 355, l. -6: "we" -> "be" (Thanks to Jacinth H.T. Wu).

p. 366, reference 3: The correct capitalization and diacritical marks are: `\"Uber formal unentscheidbare S\"atze der Principia Mathematica und verwandter Systeme´´, Monatshefte f\"ur Mathematik und Physik, Monatshefte für Mathematik und Physik" (Thanks to Jörg Bredno and Christian Lemburg).

p. 379, l. 2: "A efficient" -> "An efficient" (Thanks to Chittaranjan Tripathy).

p. 396, l. 7: the final pair should be ($,*$) (Thanks to Zeki Bayram).

p. 400, Fig. 9.15, Rule (3), lines 6-7: The # at the end of List B for the transitions delta(q_2,0) should not be there (Thanks to Ed Luke).

p. 415, l. 15: "that" -> "than" (Thanks to Christian Lemburg).

p. 422, beginning of Section 10.1.6: We do not need to say twice that L is in NP (Thanks to Mustafa Sait-Ametov).

p. 423, l. -10" "in" -> "it" (Thanks to Christian Lemburg).

p. 432, bottom and 433, top: There is a case missing from the design of B_ij. If the state of alpha_i is adjacent to position j, then neither A_{ij} nor B_ij is true as stated. Thus, we have to add terms that make B_ij true in that case. A succinct form for B_ij is:

     (y_{i,j-1,q1} OR ... OR y_{i,j-1,qm}) OR /* state to left */
     (y_{i,j+1,q1} OR ... OR y_{i,j+1,qm}) OR /* state to right */
     ((y_{i,j,Z1} OR ... OR y_{i,j,Zr}) AND   /* state at least 2 positions away
      ((y_{i,j,Z1} AND y_{i+1,j,Z1}) OR ... OR (y_{i,j,Zr} AND y_{i+1,j,Zr})))
                        /* and symbol doesn't change */

(Thanks to Zeki Bayram).

p. 433, l. -3: A_ij should be B_ij (Thanks to Christian Lemburg).

p. 435, Ex. 10.2.2, l. 3: quotes needed after j. (Thanks to Mustafa Sait-Ametov).

p. 445, item 1, l. 1: no capital for "Introduce" (Thanks to Christian Lemburg).

p. 452, l. -16, -15: The edge-cover problem is really polynomial-time (Thanks to Christian Lemburg).

p. 458, l. -2: Capitalize "Hamilton" (Thanks to Mustafa Sait-Ametov).

p. 465, l. -18: "time limit" needs quotation marks around it (Thanks to Christian Lemburg).

p. 475, l. 6 of proof of Theprem 11.4: right parenthesis missing at end of exponent on c (Thanks to Chittaranjan Tripathy).

p. 495, l. -11, "and accepting" -> "an accepting" (Thanks to Chittaranjan Tripathy).

Also, thanks to Darren Brown, David Brumley, Michael Dautermann, Gabor Hardy, Rakesh Kumar, Troy Landers, Terry Lewis, Heather Mahaney, Prashant Shah, Jackie Song, Alexei Stanger, Rod Topor, Chittaranjan Tripathy, Paavo Turakainen, Tom Whaley, Jacinth H.T. Wu, and Ivan Zdanov for correcting errors in the posted solutions.