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

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

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

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 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 161, last word of the solution to Problem 2.8.
Change her to him.
Reported 9/12/12 by Alex Arkhipov of MIT.

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

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 133, third line of proof of Theorem 2.42.
Reported 10/30/12 by Sam Stewart of Lewis & Clark College.

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 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 173, Figure 3.10.
Change the label on the self-loop transition on state q6 from 0,1,x→L to x→L. (The removed transitions are not necessary.)

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 453, index.
Reported 12/11/12 by Cem Say of Boğaziçi University, Istanbul, Turkey.
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 212, Problem 4.28.
Found 9/17/13.

Page 93, Problem 1.68, line 2.
Reported 9/17/13 by Allen Nguyen from UC Berkeley.
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 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 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 440, Problems 10.17 and 10.18, first line of each.
Change A to A⊆{0,1}*.
Found 12/1/13.

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 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 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 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 93, Problem 1.68, line 4.
Change in placed to is placed.
Reported 4/9/15 by Aaron Sipser of BB&N.

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

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 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 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 448, index entry ℛ (real numbers).
Remove 185.
Reported 4/6/16 by Peter Landweber of Rutgers 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 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 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, proof of Lemma 2.41, third line.
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, eighth line.
Change a ∈ Γ to a ∈ Σ.
Reported 2/11/18 by Eli Gray of MIT.

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 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 12, fourth line.
Change three nodes to three distinct nodes.
Reported 6/28/18 by Jeremy Roach.

Page 133, second paragraph of the proof of Theorem 2.42.
To fix a bug in this proof, add the following two blocks of text.
1. In the sentence beginning Thus followng the comma, add consider two cases. First case, if δ(q, b, ε) = ∅  for every b ∈  Σ then .
2. Before the sentence beginning Finally, add Second case, if δ(q, b, ε) ≠ ∅  for some b ∈  Σ, then add a new state qa and modify δ so δ(q, a, ε) = (qa , ε) and δ(qa , ε, x) = (r, y). Designate q to be a reading state. Observe that the rule δ(q, b, ε) ≠ ∅  is incompatible with δ(q, ε, z) ≠ ∅  for any stack alphabet symbol z. Therefore adding the rule δ(q, a, ε) = (qa , ε) will not violate determinism.
Reported 10/18/18 by Yingkang Cao of Peking University.

Page 213, Solution 4.5.
Remove where M is a TM: and add the following as the first step Check if M is a TM description and accept if it is not.
Reported 1/17/19 by Utkan Gezer of Boğaziçi University, Istanbul, Turkey.
Erratum corrected 8/24/22 by Fujioka Atsushi of Kanagawa University.

Page 135, ninth line.
Change qF to qR0.
Found 6/25/19.

Page 135, twelveth line.
Change δ(q, a, ε) to δ(q, ⊣, ε).
Found 6/25/19.

Page 128, third paragraph of Example 2.36.
Change "stipulates that either v or y is nonempty. Then we consider" to "stipulates that v or y is nonempty. Condition 3 implies that vxy cannot contain all three types of alphabet symbols. Therefore uv2xy2z cannot contain equal numbers of the three types and hence uv2xy2zB, a contradiction. An alternate argument that doesn't require Condition 3 follows. We consider".
Reported 12/11/19 by Ali Mohamed Abdelhamid Abdelfattah Kabil of the German University in Cairo and 5/9/20 by Brian Tagle and Michael Campbell of UCLA.
Page 139, seventh line of the second to last paragraph.
Reported 6/16/20 by Chen YuanYuan of NanYang Technological University.

Page 7, second line of Example 0.7.
Add where i and j are integers before the closing brace.
Reported 1/19/20 by Hamir Mahal of San Jose State University.

Page 132, proof of Lemma 2.41, last paragraph.
On the fourth line,
1. Add it pops x, after stack,.
2. Add In addition, say that (q, ε) is a looping situation if when P is started in state q, it never pops the current top symbol of the stack and never reads an input symbol. after input symbol.
On the sixth line, change If to For x ∈ Γε , if.
Reported 8/14/20 by David Liu of MIT.

Page 236, line 8.
Change Clearly, if w ∈ A then f(w) ∈ B to We know that w ∈ A whenever f(w) ∈ B.
Reported 10/9/20 by Miquel Bofill of the Universitat de Girona.

Page 115, line 5 of Example 2.16.
Remove the comma following match.
Reported 2/19/21 by Loren Schwiebert of Wayne State University.

Page 11, lower half of page.
Add a subset of before the edges of H.
Reported 8/17/21 by Darren Yin.

Page 112, third line of third paragraph after Figure 2.12.
Change very large to arbitrarily large.
Reported 10/17/21 by Isaac Levy of the University of Vermont.

Page 124, paragraph before Corollary 2.32.
At the end of the paragraph add This fact was also previously shown by using CFGs in the first paragraph of page 107.
Reported 10/17/21 by Isaac Levy of the University of Vermont.

Page 44, third line from bottom.
Remove different after two.
Reported 6/3/22 by Liam Keliher of Mount Allison University.

Page 45, sixth line from bottom.
Change accept to accepts.
Reported 6/3/22 by Liam Keliher of Mount Allison University.

Page 140, ninth and seventh text lines from bottom.
Change both occurrences of ϵ-moves to ε-moves.
Reported 6/15/22 by Fujioka Atsushi of Kanagawa University.

Page 143, second and sixth lines.
Change both occurrences of ϵ-move to ε-move.
Reported 6/15/22 by Fujioka Atsushi of Kanagawa University.

Page 144, third sentence of third paragraph of proof.
Change y in place of y' to in place of y'.
Reported 6/29/22 by Fujioka Atsushi of Kanagawa University.

Page 242, last four lines.
Remove the sentence beginning with Additionally.
Reported 8/2/22 by Kazuo Ohta of the National Institute of Advanced Industrial Science and Technology in Japan.

Page 226, last line of second paragraph.
Change isn't to doesn't.
Reported 8/23/22 by Kazuo Ohta of the National Institute of Advanced Industrial Science and Technology in Japan.

Page 161, Solution to 2.8.
Change all occurrences of to .
Reported 8/24/22 by Fujioka Atsushi of Kanagawa University.

Page 214, eighth line of Solution to 4.23.
Change ε transitions to ε-transitions.
Reported 8/24/22 by Fujioka Atsushi of Kanagawa University.

Page 446, Reference 66.
Change 2d ed. to 2nd ed.
Reported 12/25/22 by Fujioka Atsushi of Kanagawa University.

Page 172, Figure 3.8.
Remove the label x→R on the downward transition from state q1. (The removed transition is not necessary.)
Reported 4/19/23 by Behzad Hejrati from Wayne State University.

Page 109, second paragraph of proof of Theorem 2.9.
In the second sentence, add new before start variable.
Replace the last sentence with We repeat these steps until the grammar stops changing.
Reported 12/15/23 by Alfie-Joe Smith of the University of Warwick.