THIS SITE IS NO LONGER BEING MAINTAINED.
The preliminary edition is now discontinued.
It has been replaced by the first edition.
The second and third printings of the preliminary edition
fix all errors below that were reported before 5/1/96.
Ordered by appearance in the text.
Also available in order of discovery.
Last updated 12/13/96. Don't forget to reload this page to get the most
current version.
Page 2, Italicized sentence.
Change "What make ... " to "What makes ... "
Reported 4/5/96 by David Chow of the Georgia Institute of Technology.
Page 7, first paragraph, last line.
Change "input values is" to "input value is".
Reported 9/25/96 by C.R. Hale of the California State University at
Hayward.
Page 8, paragraph defining "property", line 3.
"output" should be "input".
Reported 9/3/96 by Isam M. Abdelhameed of the University of Illinois at
Chicago.
Page 11, Figure 0.7.
Exchange G and H.
Reported 3/2/96 by Joseph Raj of the University of Illinois.
Page 12, description of Figure 9.
Add (1,5), (6,3), and delete (1,6), (1,3).
Reported 1/19/96 by Tad Murata of the University of Illinois.
Page 25, Problem 0.11.
The induction step should begin "For k>=1", instead of "For k>1".
Found 1/12/96
Page 37, Figure 1.9.
Add self loops with label 0 on states q1 and q2.
Reported 1/17/96 by Tad Murata of the University of Illinois.
Page 41, Figure 1.13.
Exchange the labels 0 and 1 on the two arcs between states q and q0.
Reported 12/30/95 by Tad Murata of the University of Illinois.
Page 44, Theorem 1.12.
"A \circ B" should be "A1 \circ A2".
Reported 3/28/96 by Yaakov Eisenberg of the Georgia Institute of
Technology.
Page 48, second paragraph, line 5.
Remove extra "as".
Reported 12/1/96 by Michael Halper of Kean College.
Page 48, Figure 1.18.
Change state q101 to be an accept state.
Reported 1/24/96 by Tad Murata of the University of Illinois.
Page 50, 2nd to last paragraph, 2nd to last line.
r_i should be r_{i+1}.
Reported 2/26/96 by Rolfe Blodgett of Rutgers University.
Page 53, first sentence in third paragraph.
Change both "1"s to "2"s.
Reported 3/12/96 by Leonard Schulman of the Georgia Institute of
Technology.
Pages 53-54, Figures 1.21 and 1.22.
Exchange the labels a and b on the two arcs between states {2,3}
and {1,2,3}. In Figure 1.21, delete the b-arrow from state {1,2} and
add label b to the a-arrow from {1,2}.
In the text preceding Figure 1.21, replace {2} by {2,3}.
Reported 1/17/96 by Tad Murata of the University of Illinois.
Page 58, Figure 1.25.
Make the new start state an accept state and the old start state a
non-accept state in N.
Reported 1/25/96 by Tad Murata of the University of Illinois.
Page 61, Item 8.
01 should be 01*.
Reported 1/26/96 by Tad Murata of the University of Illinois.
Page 61, Item 9.
Replace { ..., 0, 101} by { .., 0, 1, 01}.
Reported 1/17/96 by Tad Murata of the University of Illinois.
Page 62, proof, part 1.
"... for some a in Sigma" (rather than Sigma*).
Reported 3/12/96 by Leonard Schulman of the Georgia Institute of
Technology.
Page 62, proof, part 1, last line.
Change "q2" to "{q2}".
Reported 10/3/96 by Manrique Mata-Montero of the Memorial University of
Newfoundland.
Page 63, line preceding Figure 1.26.
Change "3" to "2".
Reported 9/6/96 by Rhonda A. Reumann of Smart Interface, Inc.
Page 64, Figure 1.27.
Our definition of a GNFA doesn't allow multiple accept states,
so change the double circle around the start state to a single circle.
Reported 9/23/96 by Isam M. Abdelhameed of the University of Illinois at
Chicago.
Page 66, last line.
qk should be qj.
Reported 6/96 by an anonymous reviewer.
Page 67, "Convert" procedure, step 3, first line.
q_reject should be q_start.
Reported 3/12/96 by Leonard Schulman of the Georgia Institute of
Technology.
Page 68, 8 lines before Example 1.32.
Change "the the" to "the.
Reported 3/12/96 by Leonard Schulman of the Georgia Institute of
Technology.
Page 69, line 5.
Change "arrows" to "arrow".
Reported 9/16/96 by Kevin Jiang of McGill University.
Page 69, line 6.
"1 to 2" should be "1 to a". Remove "the" before "(b)".
Reported 8/11/96 by Hideo Nagahashi of New Mexico State University.
Page 70, Figure 1.31.
In (c), the label from 2 to 3 should be ab and the label from 3 to 2
should be ba U a.
In (d) and (e) change all occurrences of ba to (ba U a).
Reported 1/29/96 by Tad Murata of the University of Illinois.
Page 70, Figure 1.31. (second printing only)
The label on (e) is missing two left parentheses. The label should be:
(a(aaUb)*abUb)((baUa)(aaUb)*abUbb)*((baUa)(aaUb)*Ue)Ua(aaUb)*
^ ^
Reported 9/9/96 by Rhonda A. Reumann of Smart Interface, Inc, and by
Mike Ehrlich of MIT.
Page 72, Figure 1.32.
The state sequence should start "q1,q3,q20" instead of "q1,q1,q20".
Reported 9/20/96 by G. Allen Morris III of UC Berkeley.
Page 73, line preceding and 2nd & 3rd lines after Figure 1.33.
Change q52 to q13.
Reported 1/25/96 by Tad Murata of the University of Illinois.
Page 73, last two paragraphs.
The variable "l" should not be used for two different purposes
as occurs in this proof of the pumping lenna. For clarity, subtitute
the variable "k" for "l" as follows to differentiate the two meanings.
Change both occurrences of "q_l" to "q_k".
Change both occurrences of "l<=l+1" to "k<=l+1".
Change "s_{l-1}" to "s_{k-1}" and "s_l" to "s_k".
Change "j \neq l" to "j \neq k".
Reported by Rick Regan of the IBM T.J. Watson Research Center.
Page 73, 3rd line from bottom.
Change q_n to q_{n+1}.
Reported 5/8/96 by Constantine Papageorgiou of MIT.
Page 73, 2nd line from bottom.
"|y| \neq \epsilon" should be "|y| > 0".
Reported 9/17/96 by Sibel Adali of the Rensselaer Polytechnic Institute.
Page 75, Exercise 1.1 part e.
"through" instead of "though".
Reported 10/25/96 by Farzan Fallah of MIT.
Page 76, Exercise 1.4 (d).
Delete the word "of".
Reported 4/17/96 by Yaakov Eisenberg of the Georgia Institute of
Technology.
Page 76, Exercise 1.10b.
Missing parenthesis. It should read:
b. (((00)*(11)) U 01)* .
Reported 2/6/96 by Michael Rintzler of Rutgers University.
Page 77, Exercise 1.12, part (c). [See 9/17/96 error report below]
The transition function should have two additional lines in its definition.
delta(q,a) = {q1} q=q0, a=emptystring
{} q=q0, a!=emptystring
Reported 11/22/95 by Christopher Van Wyk of Drew University.
Page 77, Exercise 1.12, part (c).
The preceding erratum [11/22/95] did too good
a job of repairing this construction, so that it now works correctly even
though the problem asks for a counterexample.
Here is the entire problem restated.
Give a counterexample to show that the following construction fails to
prove Theorem 1.22, the closure of the class of regular languages under
the star operation.
Let N1=(Q1,\Sigma,\delta1,q1,F1).
Construct N=(Q1,\Sigma,\delta,q1,F) where
a) The states of N are the same as the states of N1.
b) F = F1 U {q1}. The accept states of N are the same as the accept
states of N1 with the addition of the start state.
c)
delta(q,a) = delta1(q,a) q \in Q1 and q \notin F1
delta1(q,a) q \in Q1 and a != emptystring
delta1(q,a) U {q1} q \in F1 and a = emptystring
Reported 9/17/96 by David M. Martin Jr. of Boston University.
Page 78, Exercise 1.14.
Part a) Remove the words "is not regular"
Part b) Change "has" to "is".
Reported 9/8/96 by Hjalmtyr Hafsteinsson of the University of Iceland.
Page 82, Figure 2.1.
Add one more A between the third A and B.
Reported 8/11/96 by Hideo Nagahashi of New Mexico State University.
Page 84, line 5.
The definition of the language of a grammar should require that w be a
string of only terminal symbols.
Reported 4/9/96 by Ambuj Singh of the University of California at Santa
Barbara.
Page 92, line 4.
Should say
(r ,b) \in delta(r ,w ,a)
i+1 i i+1
instead of
delta(r ,w ,a) = (r ,b)
i i+1 i+1
Reported 1/30/96 by Steve Seiden of UC Irvine.
Page 92, line 6.
Add "to" after "according".
Reported 12/1/96 by Michael Halper of Kean College.
Page 94, Figure 2.7.
The state labeled q0 should be labeled q6.
Reported 1/30/96 by Steve Seiden of UC Irvine.
Page 97, line 4.
The right-hand side of the "=" should read "{(q3,wl-2)},"
instead of "{(q2,wl-2)},".
Reported 9/10/96 by Mike Ehrlich of MIT.
Page 97, caption of Figure 2.10.
Replace equation by "{r,xyz} \in \delta{q,a,s)".
Reported 12/1/96 by Michael Halper of Kean College.
Page 98, Figure 2.12.
The 2nd arc label in the loop doing the rule, T -> Ta, should be e, e->T,
instead of e, e->a, where e = epsilon.
Reported 2/22/96 by Tad Murata of the University of Illinois.
Page 100, 4 lines before Claim 2.17.
Change "q to r" to "p to r".
Reported 10/23/96 by Farooq Mohammed of the University of Illinois.
Page 105, line 2.
Add "an" before "unequal".
Reported by Rick Regan of the IBM T.J. Watson Research Center.
Page 105, 4th line from end of Example 2.21.
"or more a's than b's" should be "or more a's than c's".
Reported 4/24/96 by Ambuj Singh of the University of California at Santa
Barbara.
Page 105, Example 2.22, 2nd paragraph, 3rd line.
Word "chose" should be "choose".
Reported 4/23/96 by Kyoung Hwan Yun of the University of California at Santa
Barbara.
Page 105, 8 lines before bottom.
Change "wxy" to vxy".
Reported 3/28/96 by Tad Murata of the University of Illinois.
Page 106, Exercise 2.3 part a.
Example 2.21 should be Example 2.20.
Reported 11/4/96 by David M. Martin Jr. of Boston University.
Page 107, Exercise 2.17 part b.
"is not a CFL" instead of "not a CFL".
Reported 10/25/96 by Farzan Fallah of MIT.
Page 111, line 2 of Section 3.1.
Insert "a" before "finite automaton".
Reported 1/15/96 by Christopher Van Wyk of Drew University.
Page 116, after Definition 3.2.
"an TM" should be "a TM".
Reported 1/15/96 by Christopher Van Wyk of Drew University.
Page 117, Example 3.5.
In Stage 3 change "left" to "right".
Reported 1/15/96 by Christopher Van Wyk of Drew University.
Page 117, Example 3.5.
Stage 2: Change "reject" to "accept".
Add Stage 5: Go to Stage 3.
Reported 9/10/96 by Mike Ehrlich of MIT.
Page 119, Figure 3.4.
All dots over symbols in the tape of Turing machine S should be shifted
one symbol to the right.
Reported 1/15/96 by Christopher Van Wyk of Drew University.
Page 120, last line, and 121, top 2 lines.
The proof idea states that the machine D rejects if it finds that all of
the branches of N reject. But the description of D's algorithm in the proof
itself doesn't implement this idea. Instead, it is relegated to Exercise 3.2.
Reported 4/5/96 by Jason Murray of the University of Washington at
Seattle.
Page 122, paragraph before Corollary 3.8.
"In the preceding proof, ..." should be "We can modify the preceding proof
so that, ..."
Reported 3/29/96 by Larry Ruzzo of the University of Washington at
Seattle.
Page 123, last paragraph, first line.
Change "reverse" to "other".
Reported 3/29/96 by Jayram S. Thathachar of the University of Washington
at Seattle.
Page 129, bottom four lines.
Change both references to Stage 3 to be to Stage 4.
Reported 1/15/96 by Christopher Van Wyk of Drew University.
Page 136, line 1 after proof of theorem 4.3.
Sentence should begin: "Theorems 4.1 , 4.2, and 4.3 ....
Reported 11/18/96 by Isam M. Abdelhameed of the University of Illinois at
Chicago.
Page 138, line 1 after proof of theorem 4.6.
Should be "CFG" not "CFL".
Reported 11/21/96 by Isam M. Abdelhameed of the University of Illinois at
Chicago.
Page 139, line 7 of proof of Theorem 4.7.
"The algorithm does ..." should be "The algorithm does this ..."
Reported 3/29/96 by Christopher Van Wyk of Drew University.
Page 139, line 7 from bottom.
G and H are CFG's not CFL's.
Reported 6/96 by an anonymous reviewer.
Page 143, last line.
Add "of" before "all".
Reported 10/15/96 by Mike Ehrlich of MIT.
Page 146, display at bottom of page.
The two brackets "}" should be moved up a line.
Reported 3/26/96 by Maurice Herlihy of Brown University.
Page 148, before Figure 4.7.
"... H rejects input < M, < M >>" should be
"... H rejects input < M3, < M2 >>".
Reported 3/26/96 by Maurice Herlihy of Brown University.
Page 158, proof of Theorem 5.4, step 1 of S.
"Run S on ..." should be "Run R on ..."
Reported 3/26/96 by Maurice Herlihy of Brown University.
Page 163, line 6.
Change "CFL" to "CFG".
Reported 3/28/96 by Tad Murata of the University of Illinois.
Page 164, line following Figure 5.4.
Add "to" before "push".
Reported 10/15/96 by Max Rozenoer of MIT.
Page 167, Parts 2 and 3.
Replace "Q" by "Q-{q_reject}".
Reported 12/5/96 by David M. Martin Jr. of Boston University.
Page 168, Figure before Part 5.
The last domino [# / #] is not added by Part 4 as indicated
since # is not an element of the tape alphabet. It is
added later by Part 5.
Reported 5/15/96 by Larry Roske of the University of Washington at
Seattle.
Page 169, Figure at the top of the page.
The first two dominos after [# / #] should be [2 / 2] and
[q_7 1 / 0 q_5] instead of [2 q_7 / 2 0] and [1 / q_5].
Reported 5/15/96 by Larry Roske of the University of Washington at
Seattle.
Page 171, 3 lines before last display.
"effect" should be "affect".
Reported 3/29/96 by Christopher Van Wyk of Drew University.
Page 172, Definition 5.15.
"f: Sigma->Sigma" should be "f: Sigma*->Sigma*".
Reported 3/26/96 by Maurice Herlihy of Brown University.
Page 173, 4th line from bottom.
Delete the comma after the first "element of" symbol.
Reported 4/27/96 by Larry Roske of the University of Washington at
Seattle.
Page 177, problem 5.14 part a.
Change < M > to < M,x >.
Reported 3/29/96 by Christopher Van Wyk of Drew University.
Page 177, Problem 5.15 (b).
Change "hold" to "holds".
Reported 4/27/96 by Larry Roske of the University of Washington at
Seattle.
Page 190, line 5 from bottom.
The second term of f(n) should be 2n^2 not 2n^3.
Reported 1/26/96 by Shaun Flisakowski of the University of Wisconsin.
Page 193, Definition 7.7, line 3.
"an O(t(n))" instead of "a O(t(n))".
Reported 12/9/96 by Farzan Fallah of MIT.
Page 196, line 8 from bottom.
Insert "TM" after "single-tape".
Reported 4/9/96 by Christopher Van Wyk of Drew University.
Page 199, last paragraph, third sentence.
Change "sufficient" to "practical".
Reported 4/9/96 by Christopher Van Wyk of Drew University.
Page 208, line 2.
"simulate N input w" should be "simulate N on input w".
Reported 3/26/96 by Maurice Herlihy of Brown University.
Page 211, line 6 after Theorem 7.22.
Exchange "AND, OR, and NOT" with their symbols.
Reported 12/8/96 by Joel Seiferas of the University of Rochester.
Page 212, Definition 7.24
"f: Sigma->Sigma" should be "f: Sigma*->Sigma*".
Reported 3/26/96 by Maurice Herlihy of Brown University.
Page 213, 2 lines before Theorem 7.25.
Insert "a" before "previously solved problem".
Reported 4/9/96 by Christopher Van Wyk of Drew University.
Page 214, first line after displayed formula.
Change "the the" to "the".
Reported 4/9/96 by Christopher Van Wyk of Drew University.
Page 214, beginning of fourth paragraph from the bottom.
Change "... connect all but two pairs of nodes in G."
to "... connect all but two kinds of pairs of nodes in G."
Reported 5/28/96 by Vegard Holmedahl of the University of California at
Santa Barbara.
Page 216, last line.
Definition of CIRCUIT-SAT should say that C is a satisfiable
Boolean circuit.
Reported 3/26/96 by Maurice Herlihy of Brown University.
Pages 218-220.
In the last paragraph in page 218, the book states that the contents
of a cell in the tableau is determined by the contents of three cells
in the preceding row. Instead, the contents of four cells
are required. For example, if the tableau contains:
a b q c
d
where q is a state, you may need to see c to determine d.
All subsequent references in the proof to these three cells must
be changed to refer to the appropriate four cells.
Reported 5/20/96 by Larry Ruzzo of the University of Washington at
Seattle.
Page 221, end of first paragraph of proof of Theorem 7.32.
w_{i+m} should be w_{l+m}.
Reported 3/26/96 by Maurice Herlihy of Brown University.
Page 223, 3 lines before Figure 7.12.
Change "represent to" to "represent".
Reported 4/9/96 by Christopher Van Wyk of Drew University.
Page 225-227 Figure 7.15.
This argument on page 225-227 that a Hamiltonian path must be normal
is incorrect. To fix it we need to add an extra node between
each of the pairs of nodes assigned to a clique in Figure 7.15.
Reported 11/13/96 Ran Libeskind-Hadas of Harvey Mudd College.
Page 228, last displayed formula.
Remove the bar over the x2 in the second clause.
Reported 4/25/96 by Ryota Matsuura of MIT.
Page 228, 4 lines from bottom.
Change h_i to h_j.
Reported 4/9/96 by Christopher Van Wyk of Drew University.
Page 228, line 3 from bottom.
Change "j-1" to "l-j".
Reported 11/14/96 by Max Rozenoer of MIT.
Page 228, last line.
"k 0s" should be "k 3s".
Reported 3/26/96 by Maurice Herlihy of Brown University.
Page 229, first line.
"subset of \phi" should be "\phi".
Reported 3/26/96 by Maurice Herlihy of Brown University.
Page 229, 3rd line after table.
Change x_1 to x_i.
Reported 5/8/96 by Constantine Papageorgiou of MIT.
Page 231, Problem 7.13.
Add at end: "for a language A in P."
Reported 6/1/96 by Larry Roske of the University of Washington at
Seattle.
Page 233, Problem 7.30.
"{< phi > | is a" should be "{< phi > | phi is a".
Reported 5/15/96 by Larry Roske of the University of Washington at
Seattle.