Last updated 5/20/23. Don't forget to reload this page to get the most current version.

Send additional errors and comments to: sipserbook@math.mit.edu

Page vi, fifth line of section 2.4 entry.

Change

Pages vi and viii.

In the entries for chapters 1, 8, and 9,

Page 7, second line of Example 0.7.

Add

Page 11, lower half of page.

Add

Page 12, fourth line.

Change

Page 27, Problem 0.13.

Change

Page 44, third line from bottom.

Remove

Page 45, sixth line from bottom.

Change

Page 90, Problem 1.51, third line.

Change

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.

Page 93, Problem 1.68, line 2.

Add

Page 93, Problem 1.68, line 4.

Change

Page 93, Problem 1.73.

Move this problem to Chapter 2.

Page 95, Solution to 1.4b.

In the figure at the top of the page, the rightmost horizontal arrow labeled

Page 112, third line of third paragraph after Figure 2.12.

Change

Page 115, line 5 of Example 2.16.

Remove the comma following

Page 119, sixth line from bottom.

Change

Page 124, paragraph before Corollary 2.32.

At the end of the paragraph add

Page 128, third paragraph of Example 2.36.

Change

Page 132, Lemma 2.41, last line of proof idea.

Change

Page 132, proof of Lemma 2.41, third line.

Change

Page 132, proof of Lemma 2.41, eighth line.

Change

Page 132, proof of Lemma 2.41, third paragraph.

Sixth line: add

Seventh line: add

Erratum corrected 4/6/16 by Peter Landweber of Rutgers University and 6/28/16 by Giacomo Tazzari.

Page 132, proof of Lemma 2.41, last paragraph.

On the fourth line,

1. Add

2. Add

On the sixth line, change

Page 133, third line of proof of Theorem 2.42.

Add

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

2. Before the sentence beginning

Page 135, ninth line.

Change

Page 135, twelveth line.

Change

Page 139, seventh line of the second to last paragraph.

Change

Page 140, ninth and seventh text lines from bottom.

Change both occurrences of

Page 141, first line of proof of Lemma 2.48.

Change

Page 142, line 4.

Change

Page 143, second and sixth lines.

Change both occurrences of

Page 144, third sentence of third paragraph of proof.

Change

Page 146, Figure 2.56.

Change the label of the lower right state from

Page 154, proof idea of Lemma 2.67, second line.

Change

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

Page 161, Solution to 2.8.

Change all occurrences of

Page 161, last word of the solution to Problem 2.8.

Change

Page 172, Figure 3.8.

Remove the label

Page 173, Figure 3.10.

Change the label on the self-loop transition on state

Page 179, proof of Theorem 3.16, stage 2 of algorithm D.

Remove

and 11/3/13 by Ulit Jaidee of Lehigh University.

Page 191, Solution to 3.16, last sentence.

Change

Page 212, Problem 4.28.

Add

Page 212, Problem 4.31.

Change

Page 213, Solution 4.5.

Remove

Erratum corrected 8/24/22 by Fujioka Atsushi of Kanagawa University.

Page 214, eighth line of Solution to 4.23.

Change

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.

Page 226, last line of second paragraph.

Change

Page 236, line 8.

Change

Page 242, Problem 5.36 part a.

Change

Page 242, last four lines.

Remove the sentence beginning with

Page 253, third paragraph, fourth line.

Change

Erratum corrected 4/6/16 by Peter Landweber of Rutgers University.

Page 259, lines 4 and 2 from bottom.

Change

Page 271, Problem 6.28c.

Should be marked as having the solution provided in the text.

Erratum corrected 4/6/16 by Peter Landweber of Rutgers University.

Page 312, eighth line from bottom.

Change

Page 328, Problem 7.49.

Add

Page 328, Problem 7.52.

Add

Page 329, Solution to 7.16.

Add a new stage

Renumber the other 3 stages to follow this new one.

Page 336, footnote.

Change page 350 to 351.

Page 350, Example 8.19, third line.

Remove indent.

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.

Page 440, Problems 10.17 and 10.18, first line of each.

Change

Page 447, reference 76.

Page 443, reference 8.

Change

Page 444, reference 18.

Change

Page 445, reference 43.

Change the journal to

Page 446, Reference 66.

Change

Page 447, item 73, and page 457, right column, sixth line.

In both places, change

Page 448, index entry

Remove 185.

Page 453, index.

Add