General overview
This textbook offers a modern, classroom‑tested introduction to the theory of computation targeted primarily at undergraduate computer science students. It balances formal definitions and proofs with pedagogy: learning outcomes, chapter summaries and many exercises to help students progress from fundamentals to more advanced topics. The text also highlights algebraic viewpoints, additional automata variants, and practical connections (for example, to parsing and compiler theory).
Contents & key themes
The book guides readers from mathematical preliminaries through the major models of computation and into decidability and complexity. Primary topics include:
| Chapter / Area | Major topics |
|---|---|
| Preliminaries | Sets, relations, functions, logic and proof techniques |
| Finite Automata & Regular Languages | Deterministic & nondeterministic automata, regular expressions, minimization, closure properties |
| Context‑Free Grammars & Pushdown Automata | CFGs, normal forms, parsing, pushdown automata |
| Turing Machines & Chomsky Hierarchy | Turing machines, linear‑bounded automata, context‑sensitive languages |
| Decidability & Undecidability | Decidable vs undecidable problems; reductions and classic undecidable problems |
| Complexity | Time/space resources, complexity classes such as P and NP, and related concepts |
Strengths & novel aspects
The text includes several features that distinguish it from many standard references: attention to algebraic structure of automata, coverage of additional automata variants, practical applications (notably parsing and compiler‑related topics), and pedagogical scaffolding such as chapter summaries and plentiful exercises designed for classroom use.
Who it's for
Primarily undergraduate CS students taking courses in automata theory and formal languages. Selected advanced chapters are suitable for graduate students. Also useful as a compact reference for researchers and practitioners wanting clear explanations of core topics in decidability and complexity.