| Introduction to Automata Theory, Languages, and Computation: Errata for the Third Edition |
|
| Introduction to Automata Theory, Languages, and Computation: Errata for the Third Edition |
List of Errata for the First, Second, and Third Printings/Second Edition.
List of Errata for the First and Second Printings/Second Edition.
List of Errata for the First Printing/Second Edition.
| Location | Problem | Reported By | Date Reported |
|---|---|---|---|
| p. 14, l. 18 | "Proof" should be "Prove." | Jim Diamond | 7/26/07 |
| p. 21, l. 15 | "x < 4" should be "x = 3" (the statement is actually true below 3). | Walter Hower | 5/31/10 |
| p. 53, l. -2 | "each block of" should be "any". That is, the block of five symbols can start anywhere. | Sageev Oore | 1/22/07 |
| p. 54, l. 11 | The string in reverse can have leading 0's. | Sageev Oore | 1/22/07 |
| p. 64, l. -1 | The sentence should begin "Since any of the 2n subsets of the last n positions could hold 1's and the others 0's,..." | kevin Montag | 4/14/09 |
| p. 65, Fig. 2.15 | Label qn-1 is missing from the empty circle. | George Tagviashvili | 8/4/06 |
| p. 71, l. -1 | The NFA's should recognize the sets of strings ending in one of the strings listed. | Markus Klinik | 6/1/09 |
| p. 74, Fig. 2.20 | State q0 needs an arrow and state q5 needs a star. | Juan Carlos Garcia Ojeda | 6/16/11 |
| p. 75, 3 lines above Sect. 2.5.4 | "my" should be "by". | Nabeel Alzahrani | 1/26/07 |
| p. 77, Example 2.21, l. 2 | "an DFA" should be "a DFA". | Pierre Flener | 1/16/07 |
| p. 83, l. -3 | "nervious" should be "nervous". | Walter Hower | 1/16/08 |
| p. 87, l. 21 | Li has at most 2i members. | San Skulrattanakulchai | 3/26/08 |
| p. 88, l. -8, -7 | "is a variable, representing" should be "is intended to represent". | Jim Diamond | 11/19/07 |
| p. 98, l. 20 | Delete "some" before "state q". | Pierre Flener | 1/16/07 |
| p. 129, title of Fig. 4.1 | "longer than" should be "at least as long as". | San Skulrattanakulchai | 3/26/08 |
| p. 136, paragraph above Closure Under Intersection | All occurrences of L should be Leq. | San Skulrattanakulchai | 3/26/08 |
| p. 138, Fig. 4.4 | Arrow missing from the arc from Start to pr. | San Skulrattanakulchai | 3/26/08 |
| p. 140, l. 12 and 14 | L(E should be L(E1) on line 12, and L(ER should be L(E1R) on line 14. | San Skulrattanakulchai | 3/26/08 |
| p. 148, Exercise 4.2.6 (b) and (c) | It should be made clear that x is a string. | 4/28/08 | |
| p. 151, l. 19 | "and" should be "an". | Steven Bills | 4/20/07 |
| p. 170, l. 1 | "modifications" should be "relations" | Mohammad Alanazi | 7/30/06 |
| p. 179, l. -3 | Period missing after "symbol". | Juan Garcia-Ojeda | 2/21/07 |
| p. 186, l. 13ff | The statement about leftmost or rightmost derivations for sentential forms with variables in them is not strictly true. You need to redefine a left/right-most derivation to skip over variables that are never expanded in the sentential form in question. | wlodek Drabent | 12/11/13 |
| p. 189, l. -3 | "classes" should be "class". | Pierre Flener and Tim Nelson | 1/16/07 |
| p. 200, l. 6 | "elements" should be "items". | Pierre Flener | 1/16/07 |
| p. 209, l. -1 | The grouping of Fig. 5.17(b) is correct, but you would replace the * by +. | Pierre Flener | 1/16/07 |
| p. 237, l. 2 | "classes" should be "class". | Pierre Flener | 1/16/07 |
| p. 240, caption of Fig. 6.7 | The second PN should be PF. | Roberto Gonzalez Cardenete | 6/22/09 |
| p. 250, l. 14 | x should be w. | Giovanni Pighizzini | 11/4/08 |
| p. 253, l. 6 | "it" should be capitalized at the beginning of the sentence. | Naomi Nishimura | 11/17/06 |
| p. 255, l. 12-13 | "0m110m for some m ≠ n" should be "0n110m for some m > n". | Andrew P. Black | 6/2/10 |
| p. 257, l. -12 | "Automata" should be "Automaton". | Pierre Flener | 1/16/07 |
| p. 270, l. -2, -1 | The grammar really is implicit in the table of Fig. 7.1. All we have to do is collect the productions. | Pierre Flener | 1/16/07 |
| p. 300, l. 18 | There needs to be an a immediately after the arrow. | Torben Amtoft | 5/28/09 |
| p. 302, l. 19 | It is only the remaining question marks that become "no." | Pierre Flener | 1/16/07 |
| p. 312, Problem 7.12, l. 6 | ``'' should be ``. | Hwang, Joonhyung | 10/20/07 |
| p. 318, l. 8 of the box | The restriction "of more than one symbol" is not necessary and should be deleted. | Torben Amtoft | 5/28/09 |
| p. 323 last line of box | "is" needed before the first "undecidable". | Zack Whyte | 11/15/09 |
| p. 328, l. -5 | Xn at the end should be Xn-1. | Naomi Nishimura | 9/13/06 |
| p. 332, l. 14 | M replaces the n+1 1's by B's and the B immediately to their left by 0. The net effect is the same as stated. | Pierre Flener | 1/16/07 |
| p. 342, l. 6 below Fig. 8.14 | The two ID's both need a "1" at the end. | Torben Amtoft | 5/23/10 |
| p. 354, l. 5 | Comma after q0. | Naomi Nishimura | 11/17/06 |
| p. 363, l. 5 | "is" should be "are". | David Ramos | 10/17/09 |
| p. 369, l. 4 | n should be in italics. | Naomi Nishimura | 11/17/06 |
| p. 374, Ref. 3, l. 2 | "verwander" should be "verwandter" and "Monatschefte" should be "Monatshefte". | Pierre Flener | 1/16/07 |
| p. 403, l. -9 | i1, i3 should be 1, 3. | Walter Hower | 6/30/10 |
| p. 432, l. -15 | "two different" should be "three different". | Torben Amtoft | 5/28/09 |
| p. 433, last line of footnote | P1 should be P2. | Marcus Ramos | 6/15/10 |
| p. 440, l. -9 | "Theorem 10.5" should be "Theorem 10.4". | Mark A. Shirley | 11/27/07 |
| p. 443, l. -3 | O(n) should be O(p(n)). | Giovanni Pighizzini | 12/9/08 |
| p. 444, l. -15 | Parenthesis needed after "state". | Jacob Moon | 6/3/10 |
| p. 454, l. 15 | "abribtrarily" should be "arbitrarily". | Torben Amtoft | 5/28/09 |
| p. 455, l. 17 | In the basis, "n=1" should be replaced by "n=1 or n=2". | Torben Amtoft | 5/28/09 |
| p. 455, l. 20 and 22 | The right side of (10.1) needs to have c as a factor. So does the expression n2-n on l. 22. | Torben Amtoft | 5/28/09 |
| p. 480, l. 2 | "probem" should be "problem". | Torben Amtoft | 5/28/09 |
| p. 482, ref. 7 | "sorting" should be "sequential search" and the pages are 265-266. | Walter Hower | 2/28/11 |
| p. 493, l. -5 | F should be E. | Wlodek Drabent | 12/11/13 |
| p. 494, l. 20 | "THe QBF" should be followed by "(11.1)". | Wlodek Drabent | 12/11/13 |
| p. 517, item 1, l. 1 | "the at most" should be "the list of at most". | Jacob Moon | 6/15/10 |
Also, thanks to Ioannis Antonellis, David Bao, Jose Brito, Darren Brown, David Brumley, Scott Craig, Michael Dautermann, Carl Eckberg, Ando Emerencia, Gabor Hardy, Rakesh Kumar, Troy Landers, Terry Lewis, Heather Mahaney, Jacob Moon, 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.