Required Reading

(1)

Text: Michael Sipser, Introduction to the Theory of Computation (3nd.\ ed., Cengage Learning, 2013). (The 2004 2nd ed.\ is completely fine, as most of the difference is in section 2.4 of chapter 2 which is skipped, and even the 1997 first edition would be OK. Page number differences for problem sets will be noted.)

(2)

Handouts and course notes provided by the instructors. Some of these will be given out in class.

The texts on reserve and course webpage are not required reading. I regard the webpage as a repository for ``static'' information such as syllabus info, problem sets, parts of answer keys, and useful links--all material that once placed on the webpage can be relied upon not to change. The newsgroup is for dynamic information--most typical are questions and helps on problem sets. Hence I regard the newsgroup as higher-priority than the webpage, and you are well advised to read it at least twice a week.

The reserve texts will include my own personal copies of the following books, on 2-hour reserve. My copy of Martin (2nd ed.) is AWOL; I will place my copy of the 3rd ed. and the rest on reserve when I am done with it.

(a)

John C. Martin, Introduction to Languages and the Theory of Computation, 3rd ed., (New York: McGraw-Hill, 1997). The text I used prior to Sipser, i.e. in the 1990s. It covers more aspects of the course material in detail than Sipser's text does, taking almost twice as many pages and including topics such as ``DFA minimization'' that Sipser cuts. The only one I intend to cover that is not in Sipser is the Myhill-Nerode Theorem, a UB(!)-Cornell product that is IMHO far superior to the "Pumping Lemma"---you you will have special notes on this.

(b)

J. Glenn Brookshear, Theory of Computation: Formal Languages, Automata, and Complexity (Addison-Wesley, 1989). The text closest to Sipser in basic nature and coverage, written by someone with a generally more ``applied'' point of view.

(c)

Harry R. Lewis and Christos H. Papadimitriou, Elements of the Theory of Computation, 2nd. ed. (Prentice Hall, 1998). A nice revision and slimming of a text that used to be rather complicated and ``heavy.'' Possibly the best text (aside from the classic 1979 mainly-graduate text by Hopcroft and Ullman, which is not on reserve) for those who really dig this material. Has also recently been used as a CSE396 text.

These are my personal copies, and are for in-library reserve only. There are various other texts in SEL that may be worth your reading. The only excursions outside Sipser's text that I am currently planning are (i) Myhill-Nerode, (ii) extra lectures on induction proofs when we hit context-free grammars leading to the topic of Structural Induction, and (iii) a lecture or two on how Turing Machines can simulate assembly language, and thus simulate ``Pascal and Lisp'' as the text asserts on page 142.