Ordered by appearance in the text.
Last updated 11/26/10. Don't forget to reload this page to get the most
current version.
Send additional errors and comments to:
sipserbook@math.mit.edu
Page 3, solution to 1.18e.
Change to: (0 ∪ 1 Σ) (Σ Σ)*
Reported 2/20/08 by Marina Blanton of the University of Notre Dame.
Page 4, solution to 1.22.
Change to: /# (#* (a ∪ b) ∪ /)* #+ / .
Reported 2/18/08 by Marina Blanton of the University of Notre Dame.
Page 5, solution to 1.29b.
Change all 0's and 1's to a's and b's.
Reported 10/10/08 by Sungbum Hong of Jackson State University.
Page 9, solution to 1.48.
Change to: 0Σ*0 ∪ 1Σ*1 ∪ 0 ∪ 1 ∪ ε
Reported 9/14/10 by Peter Drake of Lewis & Clark College.
Page 10, solution to 1.55h.
Change to:
The minimum pumping length is 4. The string 100 is in the language
but it cannot be pumped (down), therefore 3 is too small to be a
pumping length. Any string of length 4 or more in the language must
be of the form xyz where x is 10, y is in 11*0 and z is in (11*0)*0,
which satisfies all of the conditions of the pumping lemma.
Reported 3/5/07 by Joel Seiferas of the University of Rochester.
Page 15, solution to 2.6d.
Add a third line of rules:
M → aM | bM | ε | M#M
Reported 10/25/05 by Marc Smith of Colby College.
Page 18, solution to 2.22.
The solution doesn't handle the case where y begins with x
but has additional symbols. A correct PDA needs to begin by
nondeterministically deciding whether to compare the lengths of x and y,
or whether to proceed as in the original PDA. The compare-branch
accepts if the lengths are different and fails if the lengths match.
Reported 11/7/06 by Jerry Shurman of Reed College.
Page 19, solution to 2.23.
In stage 7 of the PDA, change "differs from" to "equals".
Reported 9/20/05 by Kevin Matulef of MIT.
Page 20, solution to 2.27.
In the last sentence change "rules and add" to "rule and add".
In the first added rule change "ASSIGNMENT" TO "ASSIGN".
Reported 9/20/05 by Christos Kapoutsis of MIT.
Page 21, solution to 2.29.
In the fifth from last line, "v ud x yd"
should be "u vd x yd".
Reported 10/27/06 by Cem Say of Boğaziçi University, Istanbul,
Turkey.
Page 21-22, solutions to 2.30, 2.31, 2.32.
Change 6 occurrences of "regular" to "context-free".
Reported 10/27/06 by Paliath Narendran of the State University
of New York, Albany.
Page 24, solution to 2.41.
Change both parts:
a. Let B = {aibjck|
k > 0 and (i ≠ j or k ≥ i)}.
Then
{aibici| i ≥ 0} =
(NOPREFIX(B) ∩ a*b*ccc*) ∪ abc ∪ ε,
which isn't a CFL. Hence NOPREFIX(B) cannot be a CFL.
b. Let C = {aibjck|
i ≠ j or k ≤ i}.
Then
{aibici| i ≥ 0} =
NOEXTEND(C), which isn't a CFL.
Reported 2/27/07 by Joel Seiferas of the University of Rochester.
Page 27, solution to 3.2.
New solution
Reported 11/29/05 by Marc Smith of Colby College.
Page 42, solution to 5.12.
In stage 2 of the description of T_w, add "over a non-blank symbol"
following "true blank symbol".
Reported 11/25/10 by Flavio Kuperman of the University of Michigan, Ann Arbor.
Page 42, solution to 5.14.
In stage 1, change "M moves its head" to "M' moves its head".
Reported 12/12/05 by David Kafrissen of Washington University in St. Lewis.
Page 50, solution to 6.25.
Change all "s" and "t" to "x" and "y".
Reported 10/27/06 by Cem Say of Boğaziçi University, Istanbul,
Turkey.
Page 56, solution to 7.20a.
In stages 3, change "(a,b)" to "(s,t)".
Reported 10/21/05 by Tamir Tassa of the Open University of Israel
and corrected 10/27/06 by Cem Say of Boğaziçi University, Istanbul,
Turkey.
Page 60, solution to 7.28.
In the first sentence change "in in" to "is in".
In the last line in the first paragraph, change x_l to x_m
in the subscript of C.
Reported 10/21/05 by Tamir Tassa of the Open University of Israel
and corrected 10/27/06 by Cem Say of Boğaziçi University, Istanbul,
Turkey.