CS 46 Comprehensive Final Exam is scheduled for Friday, 8 May 9am-12n in Sci 264.

Due: Wednesday, April 15

1. Write solutions to: 5.7.5 (gift if you come to class), 5.7.7 (another gift), 6.1.1, 6.FAE (below)
   
   6.FAE Extend our encoding of Turing machines to finite automata in some sensible way (one way would be to put encodings of accepting states after encoding of delta function set off by some special symbols). Now consider the language FAE = { "M" | "M" is an encoding of a DFA and L(M) is empty }. Show that the language FAE is an element of P, the class of languages decidable by TMs in polynomial time.