This updated edition of Michael Sipser's successful handbook narrates the captivating story of computation theory—a subject that encompasses elegant conclusions and exciting unanswered questions at the crossroads of mathematics and computer science.

Sipser's direct, clear style allows students of any level to understand and enjoy this intellectual field. The groundbreaking sections of "proof ideas" intuitively unveil the concepts on which the formal proofs of theorems are based, explaining fundamental ideas in everyday language.

This revised edition, which includes timely additions and more examples on key issues, maintains the established, accessible style of the book, while a new, pioneering theoretical analysis of deterministic context-free grammars facilitates the understanding of syntactic analysis and LR(k) grammars.