Ordered by appearance in the text.
Last updated 9/20/23.
Send additional errors and comments to:
sipserbook@math.mit.edu
Page 12, solution to 1.54b part iv.
Change aaa*b*c* to aaaa*b*c*.
Reported 6/16/20 by Marcus Ramos of the Universidade Federal do Vale do
São Francisco.
Page 12, solution to 1.55e,h.
Replace Part e as follows:
The minimum pumping length is 2. The string 01 is in the language,
but it cannot be divided into xyz satisfying the pumping lemma conditions
if |xy| < 1 so the pumping length cannot be 1. Pumping length 2
works because any nonempty string in the language begins with 01
and hence can be pumped by dividing it so that x = ε,
y = 01, and z is the rest.
Replace Part h as follows:
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. Pumping length 4 works
because any string s of length 4 or more in the language must begin with
101. Consider two cases. First, if the next symbol of s is 0 (thus s begins
with 1010) then we can write s = xyz where x = 10, y = 10, and z is the rest.
Second, if the next symbol of s is 1 (thus s begins with 1011) then we
can write s = xyz where x = 10, y = 1, and z is the rest. Either way
satisfies the conditions of the pumping lemma.
Reported 2/13/13 by Timothy Lewis and Charles Cusack of Hope College.
Erratum corrected 2/25/18 by William Bahn of the University of Colorado,
Colorado Springs.
Page 16, solution to 1.69b.
Change 4k+4 to 4k+5.
Line 5: Change y1 to y0 and z1 to z0 in the definition of of Q.
Line 6: Add "The start state is c0." at the beginning of the line.
Line 9: Change i to i-1 and i+1 to i in the four subscripts.
Changed 9/20/23.
Page 20, solution to 2.4b.
Change the first line of the CFG to be S → 0R0 | 1R1 | 0 | 1.
Reported 2/19/2021 by Loren Schwiebert of Wayne State University.
Page 49, solution to 4.31.
In Stage 4 of the algorithm, replace
L(K) ∩ ΣA* by
L(K) ∩ ΣA* A ΣA*
Reported 8/16/17 by Professor Malay Ananda Dutta of the Indian Institute
of Information Technology Guwahati, India.
Page 55, solution to 5.25.
Defining f so that f(ε) = ε doesn't give a
valid mapping reduction J ≤m
J.
We change it
so that f(ε) = 1. Observe that ε∉ATM
because ε doesn't encode a legal pair ‹M,w›
so the string 1ε = 1 ∈ J and hence 1∉
J.
Furthermore ε∉ J because ε doesn't have
the correct form. So f(ε) = 1 provides a mapping that
is consistent with J ≤m
J.
Reported 12/5/16 by Professor Malay Ananda Dutta of the Indian Institute
of Information Technology Guwahati, India.
Page 58, solution to 5.35a.
Change as follows: Let Sigma* = {w1, w2, ...} be a list of all
strings. The following TM N recognizes NECESSARYCFG.
N = "On input ⟨G,A⟩
1. Let GA be CFG G, except that all rules involving A are
removed.
2. For i = 1, 2, ...
3. Using the ACFG tester, if wi ∈ L(G)
and wi ∉ L(GA) then accept."
Reported 11/7/2021 by Isaac Levy of the University of Vermont.
Page 67, solution to 7.9.
Change all m variables to n variables.
Reported 9/2/2023 by Goutam Biswas of IIT Kharagpur.
Page 76, solution to 7.36.
Change (i) to be:
1k→qk
(0≤k≤m)
forces q0 to be the start state and
δ(qk , 1) = qk+1
(0≤k<m)
In (ii), change n+2 to m,
and change m to qm .
In (iv) through (xvii), change δ(q0 , 0) as follows:
(iv) δ(h , 0)
(v) δ(h , 1)
(vi) δ(vt , 0)
(vii) δ(vt , 1)
(viii) δ(vf , 0)
(ix) δ(vf , 1)
(x) δ(lt , 0)
(xi) δ(lt , 1)
(xii) δ(lf , 0)
(xiii) δ(lf , 1)
(xiv) δ(s , 0)
(xv) δ(s , 1)
(xvi) δ(r , 0)
(xvii) δ(r , 1)
Reported 7/25/15 by Bjørn Kjos-Hanssen of the University of Hawaii at Manoa.
Page 89, solution to 7.48.
Replace the part of the solution starting from We start with ... with:
First, modify G1 by adding k-k1 new nodes which
are connected to each other and to each original node. Observe that
the obtained graph G'1 has a k-clique iff G1 has
a k1-clique. Next, modify G'1 so that it cannot
have a (k+1)-clique by making k copies of its nodes. For each edge
in G'1, connect the corresponding nodes only if they are
in different copies. Call the new graph G''1.
Modify G2 to double the size of its maximum clique by making
two copies of its nodes. Connect each node with its copy and replace each
original edge with four edges connecting original nodes and copies. Call
this graph G'2 and observe that its maximum clique size is an
even number. Modify G'2 by adding (k+1)-2k2 new
nodes which are connected to each other and to each node in
G'2. Call the new graph G''2 and observe that
G''2 has a (k+1)-clique iff G'2 has a
2k2-clique iff G2 has a k2-clique.
Let G be the union of G'1 and G''2. If
G1 has a k1-clique and G2 doesn't have a
k2-clique then we've just shown that G contains a k-clique but
no larger clique. Conversely, if G's maximum clique size is k, an odd
number, the clique must be derived from a k1-clique in
G1, because a maximum clique derived from G2 would
have even size. Moreover, G2 cannot have a
k2-clique, because if it does then G would have a (k+1)-clique,
and k would not be its maximum clique size.
Reported 6/21/2021 by Yangdong Chen of Fudan University, China,
Page 92, solution to 8.26.
Replace the solution with:
Let G = (V,E). The reduction produces a graph H = (V',E') where
V' = V×V×{0,1} ∪ {s,t}
E' = {(s,(v,v,0)) | v∈V} ∪ {(t,(v,v,1)) | v∈V} ∪
{((v,x,b),(v,u,(1-b))) | (x,u)∈E}.
Reported 4/16/13 by Eric Allender of Rutgers University.