Please state any assumptions you make very clearly. Answer the questions in your own words. You must do the homework individually.

Link up to the course web page

It has been brought to my attention after the TA's grading the homeworks that some of you are using different editions of the book (or perhaps the "same" 2nd edtion has different exercises / problems). If you think that is the case, you should copy the question from the book before answering it. That will let the TA know what he is grading. But please, please, try to get the correct 2nd edition of the book, that will simplify the workload on the TA, so he does not have to grade unique problems for each student!
Link to i301 web page where Min posts copies of the homework questions for the benefit of those students who have a different version of the textbook

1. Exercise 3.8 (b), (c)
2. Problem 3.9
3. In Chapter 1, we studied how to convert an NFA into an equaivalent DFA. Can the same technique be used to show that a non-deterministic TM can be converted into an equivalent deterministic TM (as an alternate proof of Theorem 3.16)? Explain carefully.
4. Problem 3.15 (b)-(e)
5. Problem 3.16 (b)-(d)

1. Exercise 3.3
2. Exercise 3.5
3. Exercise 3.8 (a)
4. Problem 3.10
5. Problem 3.14
6. Problem 3.15 (a)
7. Problem 3.16 (a)
8. Problem 3.22