Required Text

Readings and homeworks will be assigned from "Introduction to the Theory of Computation, 2nd Edition", by Michael Sipser, PWS Publishing Company. Copies are currently available at the Columbia bookstore.

The book's website and errata are available here.

We will generally follow the book in class, but some departures are possible. Students are responsible for all material taught in class.

Optional Text

John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman
"Introduction to Automata Theory, Languages, and Computation"
Third Edition Pearson/Addison-Wesley, 2007, ISBN 0-321-45536-3