Ordered by appearance in the text.
Last updated 1/24/05. Don't forget to reload this page to get the most
current version.
Send additional errors and comments to:
sipserbook@math.mit.edu
Page 2, solution to exercise 1.13 (j).
Change 0*(100 U 010 U 001)0* to 0*(100 U 010 U 001 U 000)0*
Reported 3/9/04 by Suchitra Abel of Santa Clara University.
Page 3, solution to exercise 1.17 (b).
Solution is given for the case A_2 = {ww | w in {a,b}^*}
but the problem as stated in the text is A_2 = {www | w in {a,b}^*}.
Reported 7/23/03 by Jim Huggins of Kettering University.
Corrected 3/10/04 by Ira Gessel of Brandeis University.
Page 5, alternate solution to problem 1.23 (b).
In the first line change "C" to "C with an overline" (C complement).
At the end, change "closed under intersection" to "closed under
intersection and complement".
Reported 11/4/04 by Samir Chopra and Scott Dexter of Brooklyn College.
Pages 24-25, solution to exercise 3.4.
In the first line, change "q_accept" to "q_halt".
In line (vii), change both "q_accept" and "q_reject" to "q_halt".
In the 4th from last line, add sppace after "if".
In the 2nd from last line, change "q_accept" to "q_halt".
Reported 2/1/05 by Tamir Tassa of the Open University in Israel.
Page 27, solution to exercise 3.8 (b) and (c).
In stage 1 of both algorithms, "go to stage 4" should be "go to stage 5".
Reported 4/13/03 by Penny Anderson of Lafayette College.
Pages 28, solution to exercise 3.10.
In the 8th line, remove extra "the".
Reported 2/1/05 by Tamir Tassa of the Open University in Israel.
Pages 28, solution to exercise 3.12.
In the 1st line, add "that" after second "TM".
Reported 2/1/05 by Tamir Tassa of the Open University in Israel.
Pages 33, solution to exercise 4.5.
In the 1st line after the the TM description, remove "can be".
Reported 2/1/05 by Tamir Tassa of the Open University in Israel.
Pages 38, solution to exercise 5.4.
In the 2nd line, change "{a^n b^n| n >= 0}" to "{ab}".
Reported 2/1/05 by Tamir Tassa of the Open University in Israel.
Page 39, solution to exercise 5.13.
In the second line, change E_TM to A_TM.
In stage 1 of algorithm S, remove the sentence starting with "Finally".
Reported 9/15/03 by Jim Huggins of Kettering University.
Corrected 3/10/04 by Ira Gessel of Brandeis University.
Pages 40, solution to exercise 5.14.
In the 6th line of step 1, change "it" to "M'" for improved clarity.
Reported 2/1/05 by Tamir Tassa of the Open University in Israel.
Pages 43, solution to exercise 5.22.
In the step 2, exchange "reject" and "accept"
Reported 2/1/05 by Tamir Tassa of the Open University in Israel.
Pages 44, solution to exercise 5.23.
In the 5th line, remove "and" near the end of the line.
Reported 2/1/05 by Tamir Tassa of the Open University in Israel.
Page 56, solution to problem 7.37.
In the fourth paragraph, third sentence (starting with "Select"),
exchange the two sides of the \arrow_star so that it correctly reads
"xi \arrow_star xi\bar".
Reported 12/11/04 by Matt Low of UC Berkeley.