01 / Reading Guide
Reading Guide
Citation
Kozen, D. C. (1997). Automata and Computability. Springer.
Chapter Summary
The book is made of fifty short chapters, each between three and ten pages long, which run from page 3 to page 298 of a 400-page volume. Springer describes it as an introduction to the basic theoretical models of computability for undergraduates, in three movements: finite automata first, then pushdown automata and context-free languages, then Turing machines, ending with effective computability, decidability and Gödel's incompleteness theorems. The publisher adds that a number of supplementary chapters introduce more advanced concepts and that plenty of exercises are provided, ranging from easy to challenging. Springer's chapter list does not mark which chapters are the supplementary ones.
Chapters 1–6: Course Roadmap and Historical Perspective; Strings and Sets; Finite Automata and Regular Sets; More on Regular Sets; Nondeterministic Finite Automata; The Subset Construction
An opening roadmap with historical perspective, a chapter on the notation for strings and sets, and four chapters on deterministic and nondeterministic finite automata, ending with the subset construction.
Chapters 7–10: Pattern Matching; Pattern Matching and Regular Expressions; Regular Expressions and Finite Automata; Kleene Algebra and Regular Expressions
Pattern matching leads to regular expressions, their equivalence with finite automata, and an algebraic treatment, Kleene algebra.
Chapters 11–13: Homomorphisms; Limitations of Finite Automata; Using the Pumping Lemma
Closure under homomorphisms, then what finite automata cannot do and how the pumping lemma is applied.
Chapters 14–17: DFA State Minimization; A Minimization Algorithm; Myhill–Nerode Relations; The Myhill–Nerode Theorem
Minimization of deterministic automata, first as a concept, then as an algorithm, followed by the Myhill–Nerode relations and the theorem.
Chapters 18–22: Collapsing Nondeterministic Automata; Automata on Terms; The Myhill–Nerode Theorem for Term Automata; Two-Way Finite Automata; 2DFAs and Regular Sets
Extensions of the regular-language theory: collapsing nondeterministic automata, automata on terms with a Myhill–Nerode theorem of their own, and two-way automata.
Chapters 23–26: Context-Free Grammars and Languages; Balanced Parentheses; Normal Forms; The Pumping Lemma for CFLs
The context-free part starts with grammars, a chapter on balanced parentheses, normal forms, and a pumping lemma for context-free languages.
Chapters 27–31: Pushdown Automata; Final State Versus Empty Stack; PDAs and CFGs; Simulating NPDAs by CFGs; Deterministic Pushdown Automata
Pushdown automata, two acceptance conditions, the equivalence with context-free grammars, and deterministic pushdown automata.
Chapters 32–35: Parsing; The Cocke–Kasami–Younger Algorithm; The Chomsky–Schützenberger Theorem; Parikh's Theorem
Algorithms and structural theorems for context-free languages: parsing, the CKY algorithm, the Chomsky–Schützenberger theorem and Parikh's theorem.
Chapters 36–40: Turing Machines and Effective Computability; More on Turing Machines; Equivalent Models; Universal Machines and Diagonalization; Decidable and Undecidable Problems
Turing machines as a model of effective computability, equivalent models, universal machines and diagonalization, and the first decidable and undecidable problems.
Chapters 41–43: Reduction; Rice's Theorem; Undecidable Problems About CFLs
Reductions as the tool for showing undecidability, then Rice's theorem, then undecidable questions about context-free languages.
Chapters 44–46: Other Formalisms; The λ-Calculus; While Programs
Other formalisms for computation: the λ-calculus and while programs.
Chapters 47–50: Beyond Undecidability; Gödel's Incompleteness Theorem; Proof of the Incompleteness Theorem; Gödel's Proof
The book closes with what lies beyond undecidability and three chapters on Gödel's incompleteness theorem and its proof.
Key Concepts
Chapters 1–22: Regular Languages
- Nondeterminism and the subset construction: how nondeterministic automata are converted into deterministic ones.
- Regular expressions and Kleene algebra: equivalent descriptions of regular sets.
- Pumping lemma and Myhill–Nerode theorem: tools for proving that languages are or are not regular.
- DFA minimization: finding the smallest deterministic automaton.
Chapters 23–35: Context-Free Languages
- Context-free grammars, normal forms and the pumping lemma for CFLs.
- Pushdown automata, nondeterministic and deterministic.
- Parsing and the Cocke–Kasami–Younger algorithm.
Chapters 36–50: Computability
- Turing machines, universal machines and diagonalization.
- Reduction and Rice's theorem: ways of showing undecidability.
- The λ-calculus and while programs: other formalisms for computability.
- Gödel's incompleteness theorem.
Critical Analysis
Strengths
- Short chapters. Fifty chapters of three to ten pages can each be read at a sitting, which makes them easy to assign or to study one at a time.
- A well-paced first course. The publisher presents the book as a first course for students with some elementary discrete mathematics, with plenty of exercises from easy to challenging.
- Breadth beyond the usual core. Besides regular and context-free languages and Turing machines, the chapter list includes Kleene algebra, term automata, two-way automata, Parikh's theorem, the λ-calculus, while programs and Gödel's theorems, so the book offers choices for stronger students.
- Complete arc. The progression from finite automata through pushdown automata to Turing machines and incompleteness is visible in the order of the chapters.
Limitations
- No complexity theory. The chapter list has no chapter on time or space complexity or NP-completeness; the book ends with computability. A course that needs complexity requires another text.
- Supplementary chapters are not marked. The publisher says some chapters are supplementary, but the chapter list does not distinguish them, so a reader must choose a path.
- Mostly theoretical. Parsing and pattern matching are the only chapters with an applied flavour in their titles; readers looking for applications will find few in this book.
Where It Fits in the Course
Kozen is a compact first course in the theory of computation. Among the course books, Sipser's Introduction to the Theory of Computation is the clear upper-level introduction that continues into complexity, and the natural complement for the part Kozen omits. Hopcroft, Motwani and Ullman's Introduction to Automata Theory, Languages, and Computation is the classic larger textbook that does cover intractability. Linz and Rodger's An Introduction to Formal Languages and Automata favours explanation and worked examples, and is an alternative for readers who want more explanation than Kozen gives. MacCormick's What Can Be Computed? grounds the theory in Python programs and suits readers who prefer to start from code.
Arora and Barak's Computational Complexity is a graduate textbook on the complexity side and the natural continuation after Kozen's computability material.
How to Use This Book
Springer says students with some experience in elementary discrete mathematics will find the book a well-paced first course. Familiarity with sets, relations and proof by induction is therefore the sensible prerequisite.
A practical plan:
- Core path: Chapters 1–6 and 9 for finite automata and regular expressions; Chapters 12–13 on the pumping lemma; Chapters 23, 25 and 27–29 for context-free languages and pushdown automata; Chapters 36–42 for Turing machines, reductions and Rice's theorem.
- Selections: Kleene algebra (Chapter 10), DFA minimization and Myhill–Nerode (Chapters 14–17), parsing (Chapters 32–33) and the closing chapters on other formalisms and Gödel (Chapters 44–50), according to interest.
- Advanced: term automata, two-way automata, the Chomsky–Schützenberger and Parikh theorems.
Work the exercises as you go; the publisher stresses that plenty are provided, from easy to challenging. Pair it with a complexity text such as Sipser's if the course continues to NP-completeness.