Last updated 11/25/16. 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 27, Problem 0.13.

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 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 133, third line of proof of Theorem 2.42.

Add

Page 141, first line of proof of Lemma 2.48.

Change

Page 142, line 4.

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, last word of the solution to Problem 2.8.

Change

Page 173, Figure 3.10.

Change the label 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 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 242, Problem 5.36 part a.

Change

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 448, index entry

Remove 185.

Page 453, index.

Add