COM1350 Automata Theory Spring 2002 Homework 4

Due Monday, May 13, 2002

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

      1. (48 points)Exercise 2.4 page 120 a through f.
2. (48 points)Exercise 2.5 page 120 a through f.
Do these from scratch.
Name the states of your machines so a reader can easily tell what the machine is doing.
Do NOT use the CFG --> PDA algorithm.
You will receive no credit if you use the CFG --> PDA algorithm.

3. (4 points)

Exercise 2.12 page 121. Use the CFG --> PDA algorithm for this one.

Last Updated: March 26, 2002 5:13 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/1350hw4SP2002.html