## ERRATA for Introduction to the Theory of Computation, 3rd Edition

Ordered by appearance in the text. Also available in order of discovery.

Page vi, fifth line of section 2.4 entry.
Change LR(k) Grammars to LR(k) grammars.
Found 9/20/12.

Pages vi and viii.
In the entries for chapters 1, 8, and 9, Exercises, Problems, and Solutions, change the page numbers 82, 356, and 388 to 83, 357, and 389.
Reported 4/6/16 by Peter Landweber of Rutgers University.

Page 12, fourth line.
Change three nodes to three distinct nodes.
Reported 6/28/18 by Jeremy Roach.

Page 27, Problem 0.13.
Change graph with to graph without self-loops having.
Reported 10/28/15 by Srivatsa S. Bhat of MIT and 1/19/16 by Eric Allender of Rutgers University.

Page 90, Problem 1.51, third line.
Change whenever to iff.
Reported 10/26/13 by Jason Killian of Penn State University.
Erratum corrected 4/6/16 by Peter Landweber of Rutgers University.

Page 92, Problem 1.64.
Parts b and d should have stars to indicate their difficulty.
Reported 10/12/12 by Claude Crépeau of McGill University.

Page 93, Problem 1.68, line 2.
Reported 9/17/13 by Allen Nguyen from UC Berkeley.
Page 93, Problem 1.68, line 4.
Change in placed to is placed.
Reported 4/9/15 by Aaron Sipser of BB&N.

Page 93, Problem 1.73.
Move this problem to Chapter 2.
Found 7/8/12.

Page 95, Solution to 1.4b.
In the figure at the top of the page, the rightmost horizontal arrow labeled a should have an arrowhead on the right-hand side.
Reported 9/3/14 by Jin Soo Shin.

Page 119, sixth line from bottom.
Change is a rule in R to is a rule of G.
Reported 3/11/18 by Jeremy Roach.

Page 132, Lemma 2.41, last line of proof idea.
Change of rejects to of rejecting.
Reported 11/29/17 by Pooya Farshim of the École Normale Supérieure, Paris.

Page 132, Lemma 2.41, third line of proof.
Change for for to for.
Reported 11/29/17 by Pooya Farshim of the École Normale Supérieure, Paris.

Page 132, proof of Lemma 2.41, third paragraph.
Sixth line: add or a ∈ Σ after qF'.
Seventh line: add and a = ε after qF'.
Reported 5/27/15 by Li Juncheng of Tsinghua University.
Erratum corrected 4/6/16 by Peter Landweber of Rutgers University and 6/28/16 by Giacomo Tazzari.

Page 133, third line of proof of Theorem 2.42.
Reported 10/30/12 by Sam Stewart of Lewis & Clark College.

Page 141, first line of proof of Lemma 2.48.
Change w to z.
Reported 1/24/16 by Clelia De Felice of the Università di Salerno.

Page 142, line 4.
Change xuvy to xuvy'.
Reported 1/24/16 by Clelia De Felice of the Università di Salerno.

Page 146, Figure 2.56.
Change the label of the lower right state from T→(T). to T→T(T). .
Reported 11/23/16 by Hiroki Masuda of Waseda University, Tokyo.

Page 154, proof idea of Lemma 2.67, second line.
Change Lemma 2.67 to Lemma 2.58.
Reported 11/23/16 by Hiroki Masuda of Waseda University, Tokyo.

Page 159, Problem 2.54.
The grammar G shown in the text is not a DCFL and it fails the DK-test.
Use the following grammar instead of G.
S → T⊣
T → TaPb | TbMa | ε
P → PaPb | ε
M → MbMa | ε
Reported 6/24/13 by Lawrence Chung of Caltech.
Page 161, last word of the solution to Problem 2.8.
Change her to him.
Reported 9/12/12 by Alex Arkhipov of MIT.

Page 173, Figure 3.10.
Change the label on state q6 from 0,1,x→L to x→L. (Note, the removed transitions are not necessary.)

Page 179, proof of Theorem 3.16, stage 2 of algorithm D.
Remove and initialize the string on tape 3 to be ε from the end of the sentence.
Reported 10/26/13 by Peter Otrebus-Larsson of the Luleå University of Technology
and 11/3/13 by Ulit Jaidee of Lehigh University.

Page 191, Solution to 3.16, last sentence.
Change reject to fail to accept.
Reported 6/2/16 by Athos Ribeiro of the Institute of Mathematics and Statistics at the University of São Paulo.

Page 212, Problem 4.28.
Found 9/17/13.

Page 212, Problem 4.31.
Change CFL G to CFG G. Change wG to wL(G).
Reported 12/11/12 by Cem Say of Boğaziçi University, Istanbul, Turkey.
Page 221, Definition 5.6.
This definition of LBA implies that the tape is completely empty when the input is ε and then the machine is unable to move. This technical issue can be fixed in multiple ways, such as by adding a blank symbol after each input string or by treating ε as a special case input which the machine is designated to accept or reject.
Reported 8/14/14 by Rafi Shalom of the Open University of Israel.

Page 242, Problem 5.36 part a.
Change T-recognizable to Turing-recognizable.
Reported 11/11/13 by Tran Vinh Duc of the Hanoi University of Science and Technology.

Page 253, third paragraph, fourth line.
Change xk to xj.
Reported 11/8/12 by Stephan Boyer of MIT.
Erratum corrected 4/6/16 by Peter Landweber of Rutgers University.

Page 259, lines 4 and 2 from bottom.
Change If S finds to If P finds. Change that S fails to that P fails.
Reported 1/24/16 by Clelia De Felice of the Università di Salerno.

Page 271, Problem 6.28c.
Should be marked as having the solution provided in the text.
Found 7/8/12.
Erratum corrected 4/6/16 by Peter Landweber of Rutgers University.

Page 312, eighth line from bottom.
Change chose to choose.
Reported 4/4/14 by Adrian Kretz of the Provadis School of International Management and Technology, Frankfurt am Main, Germany.

Page 328, Problem 7.49.
Add and f(n) > n to the end of the first sentence.
Reported 8/21/14 by Ben Zinberg of MIT.

Page 328, Problem 7.52.
Add A homomorphism is nonerasing if f(a) ≠ ε for every a∈Σ, and add nonerasing before homomorphism.
Found 7/8/12.

Page 329, Solution to 7.16.
Add a new stage 1. Accept if w = ε.
Renumber the other 3 stages to follow this new one.
Reported 4/6/16 by Peter Landweber of Rutgers University.

Page 336, footnote.
Change page 350 to 351.
Reported 4/6/16 by Peter Landweber of Rutgers University.

Page 350, Example 8.19, third line.
Remove indent.
Reported 4/6/16 by Peter Landweber of Rutgers University.

Page 369, Proof of the Time Hierarchy Theorem 9.10.
The proof requires some additional technical discussion at one place. In Stage 4 of D, it simulates M on w. This simulation may require representing each cell of M's tape with several cells on D's tape because M's tape alphabet is arbitrary and D's tape alphabet is fixed. However, initializating the simulation by converting D's input w to this representation involves rewriting w so that its symbols are spread apart by several cells. If we use the obvious copying procedure for spreading w, this conversion would involve O(n^2) time and that would exceed the O(t(n)) time bound for small t.
Instead, we observe that D operates on inputs w of the form x10^k where x = ‹M›, and we only need to carry out the simulation when k is large. We consider only k > |x|^2. We can spread w by first using the obvious copying procedure for x and then counting trailing 0s and rewriting these by using that count. The time for spreading x is O(|x|^2) which is O(n). The time for counting the 0s is O(n log n) which is O(t(n)) because t is time constructible.
Reported 11/15/12 by Kaveh Ghasemloo of the University of Toronto.

Page 440, Problems 10.17 and 10.18, first line of each.
Change A to A⊆{0,1}*.
Found 12/1/13.

Page 447, reference 76.
Ullman, J. D. should be listed as the last author, not the first, and then this reference moved to page 443.
Reported 12/14/15 by Al Aho of Columbia University.

Page 443, reference 8.
Change Erdös to Erdős and similarly in the corresponding index entry on page 452.
Reported 4/6/16 by Peter Landweber of Rutgers University.

Page 444, reference 18.
Change numbers p to numbers P. Change aP-1 ≡ P to aP-1 ≡ 1.
Reported 4/6/16 by Peter Landweber of Rutgers University.

Page 445, reference 43.
Change the journal to Enseignement Mathématique 28 (1982), 191-209.
Reported 4/6/16 by Peter Landweber of Rutgers University.

Page 447, item 73, and page 457, right column, sixth line.
In both places, change Szelepczényi to Szelepcsényi.
Reported 1/31/18 by Edith Hemaspaandra of the Rochester Institute of Technology and Lane Hemaspaandra of the University of Rochester.

Page 448, index entry ℛ (real numbers).
Remove 185.
Reported 4/6/16 by Peter Landweber of Rutgers University.

Page 453, index.