Introduction to Automata Theory, Languages, and Computation: Errata for First and Second Printings Only |

List of Errata for the First, Second, and Third Printings Only.

List of Errata for the First Through Fourth Printings.

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

p. 17, l. 4: "*H* and *C*" should be "*H* and not
*C*"
(Thanks to Mark Meuleman).

p. 20, l. -14: "it" should be capitalized (Thanks to Mark Meuleman).

p. 78, l. 2: *delta* should be *delta_E*
(Thanks to Geoff Johnstone).

p. 91, 4 lines above Th. 3.4: "indictively" -> "inductively" (Thanks to Ben Pfaff).

p. 120, l. 10: hyphen in "Only if"; similar mistakes appear on pp. 178, 402, 406, 441, 442, 451, 453, 457, and 472 (Thanks to Ben Pfaff).

p. 137, l. 1: "seen only 1's" (not "0's") (Thanks to ThriBhuvan Singh).

p. 174, l. -19: "identifier" -> "expression" (Thanks to Rod Topor).

p. 174, l. -8: quotes after "steps" (Thanks to Christian Lemburg).

p. 193, l. -4: The last production body should be *iSeS*
(Thanks to Rod Topor).

p. 204, Exercise 5.3.3, l. 2: The last production body should be
*iSeS*
(Thanks to Rod Topor).

p. 225, l. 3: "turnstyle" -> "turnstile" (Thanks to Christian Lemburg).

p. 233, l. 1 of footnote: The new states are *p* and *r*
(Thanks to Jacinth H.T. Wu).

p. 236, l. -4: "and" -> "an" (Thanks to Rod Topor).

p. 238, l. -9: *P* should be *G*
(Thanks to Rod Topor).

p. 250, l. 15: "by" -> "be" (Thanks to Rod Topor).

p. 271, Exercise 7.1.2: It is safer to perform the useless-symbol elimination after eliminating epsilon-productions and unit productions. Thus, we should have asked for the steps in the order (b), (c), (a), (d). The same applies to Exercises 7.1.3 - 7.1.5.

p. 320, last line: The following is an equivalent, but clearer way to
express the move: *qX_1X_2...X_n |- pBYX_2...X_n*
(Thanks to Robert Thomson).

p. 321, l. 13: The *X_{n-1}* at the end should be *X_n*
(Thanks to Robert Thomson).

p. 324, item 1, l. 2: *m+1* -> *n+1*
(Thanks to Dmitry Shkatov).

p. 326, l. 1: *B* -> 1
(Thanks to Dmitry Shkatov).

p. 327, l. -9: "the" needed in front of "language" (Thanks to Mark Meuleman).

p. 331, bottom: The second component of the state can also be the blank (Thanks to Mike Lederle).

p. 339, l. -19: "we" should be capitalized (Thanks to Mark Meuleman).

p. 340, l. 10: "Thus if *M* starts" -> "Thus if *N*
starts"
(Thanks to Jacinth H.T. Wu).

p. 340, l. -6: "a a" -> "a" (Thanks to Jacinth H.T. Wu).

p. 354, l. 8: "and odd" -> "an odd" (Thanks to Jacinth H.T. Wu).

p. 369, first two bullets: We need to use some other variables, such as
*r* and *s* for the numbers of states and tape symbols,
because they should not be confused with the indexes *k* and
*m* used in the last paragraph on p. 369, which are particular
states and symbols.

p. 371, l. 1: delete one "consecutive."

p. 375, l. 2: "to with" -> "to do with" (Thanks to Kang-Rae Lee).

p. 391, l. 12: "let" -> "Let" (Thanks to Mustafa Sait-Ametov).

p. 397, l. 19: *i_{k+1}* -> *k+1*
(Thanks to Mustafa Sait-Ametov).

p. 397, l. 23: *z_{k_1}* -> *z_{k+1}*
(Thanks to Mustafa Sait-Ametov).

p. 399, l. -2: *a_3* -> *q_3*
(Thanks to Mustafa Sait-Ametov).

p. 408, l. -3: The argument for (f) is the "same as (e)," not "same as (f)" (Thanks to Jacinth H.T. Wu).

p. 421, l. -4: *P_1* and *P_2* are interchanged
(Thanks to Jacinth H.T. Wu).

p. 432, last line: parentheses around the entire line are needed (Thanks to Zeki Bayram).

p. 436, footnote: "Conjunction" is actually a fancy term for logical AND, not OR (Thanks to John Rappaport).

p. 438, l. -8: the middle "and" should be "an" (Thanks to Jacinth H.T. Wu).

p. 441, l. -18: delete "an" (Thanks to Ben Pfaff).

p. 442, l. 12 and 29: "If" and "Only if" labels on the proof parts are interchanged (Thanks to Jacinth H.T. Wu).

p. 442, l. 21-22: We must add to item (3) the condition that if
*T(x)* is defined, then we must choose *S(x) = T(x)*
(Thanks to Zeki Bayram).

p. 450, last line of box: delete "a" before "factor" (Thanks to Ben Pfaff).

p. 465, l. 1-3: The edge-cover problem is actually polynomial; it is a
special case of 2SAT.
Here is a similar substitute problem that *is* NP-complete:
The *feedback edge problem*:
given a graph *G* and an integer *k*, does there exist a set
of *k* edges such that every cycle of *G* has at least one
edge in the cycle?
(Thanks to Richard Lorentz).

p. 467, last line: "10.4.4(d)" should be "10.4.4(g)" (Thanks to Junghoo Cho).

p. 468, ref. 2: Period needed in "A. Cobham" (Thanks to Kang-Rae Lee).

p. 472, l. 21: "*L* is in *NP*" should be "*L-bar*
(i.e., *L* with a line above) is in *NP*"
(Thanks to Jacinth H.T. Wu).

p. 477, l. -7: Omit "log_2" from the formula for *m*
(Thanks to Zeki Bayram).

p. 491, l. 16: delete "are" (Thanks to Zeki Bayram).

p. 493, item (3), line 1: *p(n)* -> *T(n)*
(Thanks to Zeki Bayram).

p. 494, l. 16: "none of" -> "at least one of" (Thanks to Zeki Bayram).

p. 501, l. 14: "throwing away" -> "then computing" (Thanks to Zeki Bayram).

p. 502, l. 17: add "modulo *p*" at the end
(Thanks to Zeki Bayram).

p. 510, ref. 4: The date, 1972, is missing (Thanks to Zeki Bayram).