Introduction to the Theory of Computation

Textbook for an upper division undergraduate and introductory graduate level course covering automata theory, computability theory, and complexity theory.

The second edition was published in February 2005. It includes many new exercises and problems with some sample solutions, in addition to various other improvements over the first edition. I am maintaining a list of errata for the second edition.

The first edition has been discontinued.
I am no longer maintaining its errata site.

The preliminary edition had been discontinued.
I am no longer maintaining its errata site.