Introduction to Automata Theory, Languages, and Computation: Errata for the First through Fourth Printings
    List of Errata for the First, Second, and Third Printings Only.

    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 fourth printing:

    LocationProblemReported ByDate Reported
    p. 5, l. 1 A correct expression is '[A-Z][a-z]* ([ ][A-Z][a-z]*)*[ ][A-Z][A-Z]' Daniel Suen 8/16/02
    p. 20, l. 5 "a least" -> "the least" Brandon Gray 9/10/02
    p. 24, box, l. -3 "of" needed after "validity" Robert Robinson 5/26/03
    p. 24, l. -4 add "hold" after S(Yk) Robert Yamins 2/7/04
    p. 72, l. 1 Add q0 to the list of states whose transitions on x must be taken. Steven Bique 2/21/05
    p. 72, l. 10 "out or" -> "out of" Allan Bullwinkel 9/5/04
    p. 75, bottom We need to add the definition of the extension of ECLOSE to sets of states. That is, ECLOSE(S) = ∪q in SECLOSE(q). Scott Craig 5/16/05
    p. 96, l. 17-18 The expressions are for the R(k)'s, and they contain the subsexpression (Rkk(k-1))* Nezam Mahdavi-Amiri 1/22/03
    p. 111, l. 7 The = sign is assignment, not EQ, in C, so a more appropriate symbolic constant to return would be ASGN Massazza Paolo 3/28/03
    p. 126, l. 1 Capitals needed in title of section Wang Zirui 4/22/04
    p. 132, l. 3, 4 The sets {a,b} and {b,c,d} should be closed, i.e., {a,b}* and {b,c,d}*. Aaron Windsor 2/23/04
    p. 133, l. -2 Delete second "and" Nezam Mahdavi-Amiri 1/30/03
    p. 146, Exercise 4.2.3, l. 1 "Lf" -> "If" Brandon Gray 10/30/02
    p. 147, l. -1 L* = ε + 000* Virginia Stoll 4/9/03
    p. 151, l. 12 The correct expression for the running time is O(8n42n) Steven Bique 3/9/05
    p. 152, l. 16 "that" -> "than" Robert Robertson 9/19/03
    p. 164, l. -3 First "are" -> "and" Dongsoo Jang 4/23/02
    p. 165, l. -16 {E,G} is also discovered to be distinguishable on the second round. The argument is the same as for {A,G}. Shaojun Zhao 1/9/05
    p. 165, l. -3 "addition" -> "additional" James Nichols (recorrection by Sui Huang) 2/25/03
    p. 166, reference 4 Date is 1971 Nezam Mahdavi-Amiri 1/30/03
    p. 177, Sect. 5.1.5, l. 1 "=" needed after G in G(V,T... Jose Brito 8/28/02
    p. 189, l. 13: A -> E Alexey Sarytchev 11/26/02
    p. 198, l. 21 "are" -> "is" Nezam Mahdavi-Amiri 2/4/03
    p. 200, l. 11 Terminating > needed on the declaration for HARDDISK Aaron Windsor 3/2/04
    p. 201, l. -3 "Is" -> "is" Nezam Mahdavi-Amiri 2/4/03
    p. 213, l. -9 b -> b's Madhu Mutyam 9/12/03
    p. 214, l. 3 delete "| ab" from the productions for A2 Alexey Sarytchev 11/26/02
    p. 234, l. 1-2 hyphen needed in "bottom-of-stack" Nezam Mahdavi-Amiri 2/21/03
    p. 235, l. 15, 16 single left quotes should be double quotes Magdiel Galan 4/30/02
    p. 238, l. -3 "terminals" -> "input symbols" John Custy 9/6/05
    p. 244, l. -12 State q should be q0 Zeki Bayram 8/24/04
    p. 243, l. -13 pi -> ri Madhu Mutyam 9/18/03
    p. 253, l. 9 "generate" -> "generates" Nezam Mahdavi-Amiri 2/21/03
    p. 259, l. 20 "with out" -> "without" Jose Brito 8/28/02
    p. 260, l. 3 Delete "the" before "each" Nezam Mahdavi-Amiri 2/21/03
    p. 262, l. 10 The last symbol of the production is Ym, not Yk. Po-Lian Tsai 4/12/04
    p. 263, l. 16 Production E --> E+T was omitted. Nelson Pereira 4/27/05
    p. 268, l. -3, -4 G1 and G2 are interchanged (a total of three occurrences on these two lines). Zeki Bayram 8/24/04
    p. 287, l. 11 δA(p) should be δA(p,a). Jinoh Kim 3/5/04
    p. 271, l. 4 of box "are" -> "is" Nezam Mahdavi-Amiri 2/21/03
    p. 271, l. -7 capitalize "Normal Form" Nezam Mahdavi-Amiri 2/21/03
    p. 272, Ex. 7.1.8, l. 2 delete one "we" Nezam Mahdavi-Amiri 2/21/03
    p. 272, Ex. 7.1.8, l. 1-2 n should really be the sum of the lengths of the production right sides for G. Frank Drewes 2/7/04
    p. 276, l. -2 "CFl" -> "CFL" Nezam Mahdavi-Amiri 2/21/03
    p. 281, Exercise 7.2.5(b), l. 2 The exponent on c should be n+n! rather than just n!. Jukka Suomela 9/21/03
    p. 287, l. 15 pA should be qA. Po-Lian Tsai 4/13/04
    p. 287, l. -5 The move should be (r, ε); i.e., delete one of the ε's Kitti Sutthiatthasil 5/8/03
    p. 288, l. -3 "sees and e" -> "sees an e" Nezam Mahdavi-Amiri 2/21/03
    p. 289, l. 5 delete "a" before "CFL" Nezam Mahdavi-Amiri 2/21/03
    p. 292, l. -9 The string referred to is the fourth string, 10101, not the third string, 10110. Aaron Windsor 4/12/04
    p. 292, l. -8 comma after "01110" Nezam Mahdavi-Amiri 2/21/03
    p. 292, l. -5 "the the" -> "be the" Nezam Mahdavi-Amiri 2/21/03
    p. 293, l. -10 "and" should be ", where" Firas Bouz 4/23/03
    p. 295, l. 14, 15 The three transitions shown should have ε as the middle argument of δ. Zeki Bayram 8/24/04
    p. 295, l. -6 no capital for "See" Nezam Mahdavi-Amiri 2/21/03
    p. 297, l. -19 "suggests" -> "suggest" Nezam Mahdavi-Amiri 2/21/03
    p. 304, l. 15 captialize "Normal Form" (twice) Nezam Mahdavi-Amiri 2/21/03
    p. 310, l. -13 close-quotes needed after the question-mark Po-Lian Tsai 5/2/04
    p. 321, l. 13 Subscript n-1 at the end should be n Ning Kang 4/15/04
    p. 326, l. -4 comma after "languages" should be a period Nezam Mahdavi-Amiri 3/6/03
    p. 330, l. -14 B must be added as the blank symbol (6th) component of the specification of M William Deng 3/14/03
    p. 332, l. 9-10 [B,c] is also an input symbol, identified with c. Jukka Suomela 9/24/03
    p. 333, l. 16 "is" -> "in" Nezam Mahdavi-Amiri 3/6/03
    p. 334, l. 8 The subroutine really "helps implement" step (2) Jerônimo Pellegrini 1/23/04
    p. 334, l. 16 The second ID on that line does not have a 1 at the end. Boris Tanana 9/23/03
    p. 346, three lines below Fig. 8.19 comma after "semi-infinite" Po-Lian Tsai 5/2/04
    p. 348, l. -6 "...which, if any, of..." Po-Lian Tsai 5/2/04
    p. 354, Exercise 8.5.1(b) The condition should be m >= n >= 1. Jukka Suomela 9/24/03
    p. 360, l. 15 comma after "tape" Nezam Mahdavi-Amiri 3/6/03
    p. 360, l. -14 capitalize "find" Nezam Mahdavi-Amiri 3/6/03
    p. 361, l. -16 "between" -> "separating" Po-Lian Tsai 5/2/04
    p. 372, l. 4 Capitals needed in title of Section 9.1.4 Wang Zirui 4/22/04
    p. 373, title of Section 9.2 Capitalize "is" Wang Zirui 4/22/04
    p. 380, Theorem 9.6 since w might have three consecutive 1's, we need first to check that w is a valid Turing-machine code (which cannot have 3 1's in a row), and accept w if it does. Only if the code is valid do we simulate the hypothetical TM. Alexander L. Thomson 4/14/04
    p. 384, l. 6 of proof of Theorem 9.7 "decides to" -> "applies" Nezam Mahdavi-Amiri 3/31/03
    p. 398, l. -13 no comma after "This" Nezam Mahdavi-Amiri 3/31/03
    p. 404, l. -6 "have" -> "has" Nezam Mahdavi-Amiri 3/31/03
    p. 407, l. 8 delete "a" Nezam Mahdavi-Amiri 3/31/03
    p. 409, Exercise 9.5.3 The condition defining LAB should be that 1, 2, 3, and at least one of 4-7 hold. Rod Howell 5/6/02
    p. 413, l. -8 "implies" really should be "strongly suggests." Scott Craig 4/26/05
    p. 422, l. 8 delete second "time" Nezam Mahdavi-Amiri 3/31/03
    p. 422, l. -11 comma after "satisfiability)" Nezam Mahdavi-Amiri 3/31/03
    p. 424, l. 12 comma should appear on the previous line Andrzej Wasowski 5/30/02
    p. 425, l. 5 of text "in" -> "it" Nezam Mahdavi-Amiri 3/31/03
    p. 426, l. 6 "hold" -> "holds" Nezam Mahdavi-Amiri 3/31/03
    p. 428, l. 1 delete comma Nezam Mahdavi-Amiri 3/31/03
    p. 430, last two lines We omitted a fourth term U that says there can be no more than one yijZ for fixed i and j. U is constructed by taking the AND of all terms of the form NOT(yijW AND yijZ). Note there are on the order of p(n) such terms, and they can be written in on the order of that amount of time. Jukka Suomela 9/28/03
    p. 431, 3 lines below figure Remove comma after X0j. Po-Lian Tsai 6/16/04
    p. 434, l. 11 The term U described in the errata item for p. 430, needs to be included. Jukka Suomela 9/28/03
    p. 434, l. 13 delete "that" Nezam Mahdavi-Amiri 3/31/03
    p. 442, l. -1 F1 should be E1. Po-Lian Tsai 6/16/04
    p. 443, l. 13 "Where" -> "where" Nezam Mahdavi-Amiri 3/31/03
    p. 446, l. 10 "expand" -> "expands" Nezam Mahdavi-Amiri 3/31/03
    p. 446, Exercise 10.3.3 The description of En should say that for each i, j, and k between 1 and n, there is a clause xi+xj+xk and the same with the bars above the variables. Narendra S. Chaudhari 4/1/04
    p. 448, l. 12 "See" -> "see" Nezam Mahdavi-Amiri 3/31/03
    p. 457, l. -5 Capitalize "we". Po-Lian Tsai 6/16/04
    p. 461 l. -12 "edges of G" should be "nodes and edges of G". Po-Lian Tsai 6/16/04
    p. 463, l. -10 "are" -> "is" Nezam Mahdavi-Amiri 3/31/03
    p. 465, l. 1-3 "edges" should be "arcs," throughout. Mihalis Yannakakis 11/23/03
    p. 468, ref. 7 The correct pages are 115-116. Marcus Hutter 9/13/02
    p. 473, l. -2 "polynomial time" -> "polynomial space" Rod Howell 4/15/03
    p. 490, l. 15 "not be" -> "may not be" Nezam Mahdavi-Amiri 3/31/03
    p. 502, l. 1-2 of text "we can divide x by any nonzero number y..." Nezam Mahdavi-Amiri 3/31/03
    p. 506, l. 6 "are" -> "is" Nezam Mahdavi-Amiri 3/31/03

    Also, thanks to Ioannis Antonellis, Jose Brito, Darren Brown, David Brumley, Scott Craig, Michael Dautermann, Carl Eckberg, Ando Emerencia, Gabor Hardy, Rakesh Kumar, Troy Landers, Terry Lewis, Heather Mahaney, Juan Morales, Viet-Bang Nguyen, Raviraj Paliwal, Prashant Shah, Jackie Song, Alexei Stanger, Chang-Hsien Tsai, Rod Topor, Chittaranjan Tripathy, Paavo Turakainen, Wang Zirui, Tom Whaley, Jacinth H.T. Wu, and Ivan Zdanov for correcting errors in the posted solutions.