Help support MIT OpenCourseWare by shopping at Amazon.com! Partnering with Amazon.com, MIT OCW offers direct links to purchase the books cited in this course. Click on the book titles and purchase the book from Amazon.com, and MIT OCW will receive up to 10% of all purchases you make. Your support will enable MIT to continue offering open access to MIT courses.
This section contains the weekly homework assignments for the course. Many of the homework assignments refer to the required textbook: Sipser, Michael. Introduction to the Theory of Computation. 2nd ed. Boston, MA: Course Technology, 2005. ISBN: 0534950973.
All homework solutions for this course must be typed. The course staff highly recommend that students use LaTeX. A useful LaTeX Web site can be found here.
The students are expected to complete and turn in all homework assignments except for a few assignments that are just given so that students can practice the material covered in the lectures. The practice homework assignments are indicated below.
Homework 1 (PDF)
Homework 2 (PDF)
Homework 2.5 (PDF) (practice only)
Homework 3 (PDF)
Homework 4 (PDF)
Homework 5 (PDF)
Homework 5.5 (PDF) (practice only)
Homework 6 (PDF)
Homework 7 (PDF)
Homework 8 (PDF)
Homework 8.5 (PDF) (practice only)
Homework 9 (PDF)
Homework 10 (PDF) (practice only)
Homework 10.5 (PDF) (practice only)