COM1350 Automata Theory Spring 2002 Homework 2

Due Tuesday, April 16, 2002

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

      1. (50 points)Exercise 1.5 page 84, all parts.
2. (20 points)
a.Exercise 1.6a page 84.
b.Use the construction in the proof of Theorem 1.12 to give the state diagram of a DFA that recognizes this language.

3. (10 points)

Exercise 1.7a page 84.
4. (10 points)Exercise 1.8a page 85.
5. (10 points)Exercise 1.12b page 85.

Last Updated: March 26, 2002 3:37 p.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/1350hw2SP2002.html