WPI Worcester Polytechnic Institute

Computer Science Department
------------------------------------------

CS4123 Theory of Computation 
Homework 4 - B 2004

Due Date: Tuesday, December 14th at 12:00 noon.
NO SUBMISSIONS WILL BE ACCEPTED AFTER 12:05 PM.
 
------------------------------------------

Problems

  1. (20 points) Show that the EDFA language is in the class P:

    EDFA = {<D> | D is a DFA and L(D) is the empty set}.

    That is, show that there is a deterministic Turing machine that decides this language in polynomial time in the size of the input:

    Since the input to this problem is a DFA, state explicitly in your solutions what the size of the input is (i.e., how it is measured).

  2. (20 points) Problem 7.20 from the textbook (p. 273).

  3. (30 points) Problem 7.19 from the textbook (p. 272).

  4. (30 points) Problem 7.25 from the textbook (p. 274).

Additional Problem for Students taking the course for Graduate Credit

None this time. Just do your best on the problems above.

Homework Submission

Bring your homework solutions to the beginning of the class period. The HW is due on Tuesday, December 14th at 12:00 noon. NO SUBMISSION WILL BE ACCEPTED AFTER 12:05 PM.