COM1350 Automata Theory Spring 2002 Homework 5

Due Monday, May 30, 2002

These exercises are from or refer to Sipser, Michael, "Introduction to the Theory of Computation," PWS Publishing Company, Boston

      1. (20 points)Exercise 3.1 page 147 all parts.
2. (14 points)Exercise 3.4 page 147.
Refer to the formal definition of a Turing Machine, Definition 3.1, age 128.

3. (20 points)

Exercise 3.8b page 148.

4. (18 points)

Exercise 4.1 pages 168-169 all parts.

5. (14 points)

Exercise 4.7 page 169.

6. (14 points)

Exercise 4.8 page 169.

Last Updated: March 27, 2002 7:37 a.m. by

Harriet Fell
College of Computer Science, Northeastern University
360 Huntington Avenue #161CN,
Boston, MA 02115
Internet: automata@harrietfell.com
Phone: (617) 373-2198 / Fax: (617) 373-5121
The URL for this document is: http://www.ccs.neu.edu/home/fell/COM1350/HW/1350hw4SP2002.html