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).