Introduction to the Theory of Computation, 3rd edition

Author: Michael Sipser

Published by Cengage Learning.

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

The third edition apppeared in July 2012. It adds a new section in Chapter 2 on deterministic context-free grammars. It also contains new exercises, problems and solutions.

Please see the list of errata for the third edition.

The preliminary, first and second editions have been discontinued. I am no longer maintaining their errata sites.