Computer Science 456/656: Automata and Formal Languages

Spring 1999

Homework Assignment 8.

Due May 12, 1999

Do not hand in this assignment. Its purpose is to give you material to study in the area of computational complexity.

• Work exercise 14.6 on page 411 of your textbook.
• Work exercise 14.14 on page 411 of your textbook.
• Work exercise 15.9(a) on page 433 of your textbook.
• Work exercise 15.12 on page 433 of your textbook.