CSEP 590TU Assignment #7
Autumn 2003

Due: Wednesday, Nov 19, 2003.

Read Chapter 8, sections 8.1-8.5 of Sipser's text.

Problems

  1. Show that if L1 and L2 are in PSPACE then L1 UNION L 2 and the complement of L1 are both in PSPACE.

  2. Sipser's text problem 8.6 page 302.

  3. Sipser's text problem 8.9 page 303.

  4. Sipser's text problem 8.10 page 303.

  5. Sipser's text problem 8.13 page 303.