Introduction to the Theory of Computation

Citation

Sipser, M. (2012). Introduction to the Theory of Computation (3rd ed.). Cengage Learning.

Chapter Summary

The book is organised in three parts that follow the traditional sequence of the subject: automata and languages, computability theory, and complexity theory. A preliminary Chapter 0 comes first, and each chapter ends with exercises, problems and solutions. The author describes the book as a textbook for an upper-division undergraduate or introductory graduate course covering automata theory, computability theory and complexity theory.

Chapter 0: Introduction

The opening chapter collects the mathematical background used throughout, including sets and graphs, with numbered examples and problems. It is where the book's habit of stating definitions and theorems formally and proving them is first set out.

Part One, Chapters 1–2: Automata and Languages

Chapter 1, "Regular Languages", introduces the simplest models of computation and the languages they recognise. Chapter 2, "Context-Free Languages", moves to the next level of expressive power. The third edition added a new section here, on deterministic context-free grammars, which the publisher presents as a first-of-its-kind theoretical treatment connected to parsing and LR(k) grammars.

Part Two, Chapters 3–6: Computability Theory

Chapter 3, "The Church–Turing Thesis", introduces the Turing machine as the standard model of what an algorithm can do. Chapter 4, "Decidability", asks which problems can be solved by such machines at all. Chapter 5, "Reducibility", develops reductions as the main tool for showing that further problems are undecidable. Chapter 6, "Advanced Topics in Computability Theory", extends the part with further results beyond the core sequence.

Part Three, Chapters 7–10: Complexity Theory

Chapter 7, "Time Complexity", turns from what can be computed to what can be computed within a resource bound. Chapter 8, "Space Complexity", does the same for memory. Chapter 9, "Intractability", examines problems that are provably hard, and Chapter 10, "Advanced Topics in Complexity Theory", closes the book with further topics.

Key Concepts

Part One: Automata and languages

• Regular languages: the languages recognised by the simplest models of computation, the subject of Chapter 1.
• Context-free languages: the next class, the subject of Chapter 2, with deterministic context-free grammars added in the third edition.

Part Two: Computability

• Turing machines and the Church–Turing thesis: the formal model that stands for the intuitive notion of an algorithm.
• Decidability: whether a problem can be solved by an algorithm at all.
• Reducibility: transferring undecidability from one problem to another by a reduction.

Part Three: Complexity

• Time and space complexity: measuring the resources a computation needs, the subject of Chapters 7 and 8.
• Intractability: problems that are provably hard, the subject of Chapter 9.

Critical Analysis

Strengths

• Clarity as the publisher's main claim. Cengage describes the book as keeping an approachable style with timely revisions, additional exercises and more memorable examples, while maintaining rigour and formalism.
• A single path through three subjects. The parts follow the order in which most courses teach the material: automata first, then computability, then complexity. The titles of Chapters 3–5 show decidability and reducibility built in sequence on the Turing machine.
• Exercise support. Every chapter ends with exercises, problems and solutions; the third edition adds new exercises, problems and solutions, and the author maintains a public errata list for the edition.
• Parsing connection. The new section on deterministic context-free grammars links the theory to LR(k) parsing, which is useful for readers who meet grammars in compiler courses.

Limitations

• Proof-based throughout. The publisher stresses mathematical treatments "including advanced theorems and proofs", so readers with little proof experience should expect to learn proof-writing alongside the material.
• Theory only. The chapter list contains no programming-based material; readers who want to see computability through running programs will need another source.
• Advanced chapters are selective. Chapters 6 and 10 are collections of further topics, not a full development of any single one.

Where It Fits in the Course

Sipser is the standard-weight, proof-oriented core text in this course list. Peter Linz and Susan Rodger's An Introduction to Formal Languages and Automata is a gentler introduction that favours explanation and worked examples over heavy formalism, and John MacCormick's What Can Be Computed? grounds computability and complexity in short Python programs before the formal arguments, making it a good first book for readers who find the formal approach abstract. Dexter Kozen's Automata and Computability is organised as short lectures with full proofs and a large set of graded exercises, while Hopcroft, Motwani and Ullman's Introduction to Automata Theory, Languages, and Computation is the classic alternative with a similar scope. Arora and Barak's Computational Complexity is a graduate-level book that continues where Chapters 7–10 stop.

How to Use This Book

The book suits upper-level undergraduates and beginning graduate students who have taken discrete mathematics and can read and write proofs.

A practical plan:

• Core: Chapter 0 for notation (skim if familiar), then Chapters 1–5 and 7 in order. These give a complete first course: regular and context-free languages, Turing machines, decidability and reductions, and time complexity.
• Next: Chapter 8 on space complexity and Chapter 9 on intractability.
• Optional: the final sections of Chapter 2 on deterministic context-free grammars if you are interested in parsing, and the "advanced topics" Chapters 6 and 10 for a longer or graduate-level course.
• Practice: attempt each exercise and problem before looking at the solutions, and write proofs out in full sentences; the book's own proofs are a model for this. Check the author's errata list for the edition you own.

A reader who finds Chapters 1–2 abstract can start with a gentler or program-based book and return to Sipser for Chapters 3–5, where computability is introduced. For self-study, keep a notebook of the main reductions and proof patterns from Chapters 4, 5 and 7; reductions and proof patterns recur from chapter to chapter, and re-deriving them from memory is a quick test of understanding.