CS4123 Theory of Computation. A99
Homework 2

Prof. Carolina Ruiz
Department of Computer Science
Worcester Polytechnic Institute

Homework 2

Due on Tuesday, Sept. 21, 1999 at 5:00 p.m.
You can either turn in your homework in class or bring it to my office FL232 before 5 p.m. (If I'm not in, please slip your homework under my door).

Problems:

  1. Exercise 4.1 from the textbook.

  2. Exercise 4.3 from the textbook.

  3. Exercise 4.4 from the textbook.

  4. Problem 4.11 from the textbook.

  5. Exercise 5.1 from the textbook.

  6. Let Sigma be an alphabet. Show that
    INFINITE_TM = { < M > | M is a Turing machine and M accepts infinitely many words}
    is undecidable.
    Hint Show that A_TM <=m INFINITE_TM.

Additional Problems for students taking this course for graduate credit:

  1. Problem 4.17 from the textbook.
  2. Problem 4.22 from the textbook.
  3. Problem 5.9 from the textbook.