01 / Reading Guide
Reading Guide
Citation
Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation (3rd ed.). Pearson.
Chapter Summary
The third edition has eleven chapters in about 535 pages, so its chapters are long: the first, on the methods of the subject, runs for about 36 pages, and the second, on finite automata, for about 48. The book descends from Hopcroft and Ullman's 1979 text; Motwani joined for the second edition (2000), and the third edition appeared in 2006. Pearson describes this edition as updated to present theoretical concepts concisely and straightforwardly, with more hands-on, practical applications, and as coming originally with Gradiance, an online assessment tool that Pearson says is no longer available with the book. The chapter order follows the usual route of the subject: regular languages, then context-free languages, then Turing machines, undecidability and intractability.
Chapter 1: Automata: The Methods and the Madness
An introductory chapter of about 36 pages that sets up the subject before the first model is defined.
Chapter 2: Finite Automata
Finite automata as the first and simplest model of computation, at about 48 pages the longest of the opening chapters. The frequent terms listed for the book by Google Books include nondeterministic automata and "e-NFA", the extended nondeterministic form with empty-string moves.
Chapter 3: Regular Expressions and Languages
Regular expressions and the languages they describe, beginning on page 85.
Chapter 4: Properties of Regular Languages
The properties of regular languages, the first of two chapters with "Properties" in the title.
Chapter 5: Context-Free Grammars and Languages
Grammars as a second way of describing languages, with derivations and parse trees among the book's recurring terms.
Chapter 6: Pushdown Automata
The machine counterpart of context-free grammars, including deterministic pushdown automata (DPDA), which appear among the frequent terms of the text.
Chapter 7: Properties of Context-Free Languages
The counterpart of Chapter 4 for context-free languages.
Chapter 8: Introduction to Turing Machines
The Turing machine as the general model of computation, and the starting point for the chapters that follow.
Chapter 9: Undecidability
Problems that no algorithm can solve. The frequent terms listed by Google Books include the modified Post correspondence problem (MPCP).
Chapters 10–11: Intractable Problems; Additional Classes of Problems
Problems that can be solved in principle but not efficiently, followed by a closing chapter on further classes of problems. The frequent terms listed by Google Books include polynomial-time reduction, 3SAT, co-NP and the Hamilton circuit problem.
Key Concepts
Chapters 1–4: Regular Languages
- Finite automata: the first model of computation, taught before grammars and machines.
- Regular expressions: a notation for the same class of languages.
- Properties of regular languages: closure and decision questions.
Chapters 5–7: Context-Free Languages
- Context-free grammars and languages.
- Pushdown automata: finite automata with a stack.
- Properties of context-free languages.
Chapters 8–11: Computability and Complexity
- Turing machines: the general model of computation.
- Undecidability: problems no algorithm solves.
- Intractable problems and additional classes of problems: the limits on efficient computation.
Critical Analysis
Strengths
- A full path in eleven chapters. The contents run from finite automata through context-free languages and Turing machines to undecidability and intractability, so one book covers a whole undergraduate course.
- Intractability is included. Chapters 10 and 11 cover intractable problems and further classes, whereas Kozen's chapter list stops at computability.
- Presentation aims at accessibility. Pearson stresses concise, straightforward presentation and practical applications.
- Long track record. Three editions between 1979 and 2006, with Hopcroft and Ullman as authors throughout, have made it an influential text in the subject.
Limitations
- Less advanced theory than the older edition. Accounts of the book's history note that, beginning with the second edition, applications were extended and parts of the more advanced theory were removed. A course that needs the deeper material of the 1979 edition will want a supplementary text.
- Long chapters. At 36 to 48 pages in the opening chapters, the book is less modular than a text organised in many short chapters.
- Bundled online tool is gone. Gradiance, which accompanied the third edition, is no longer supported by Pearson, so any homework system built around it is unavailable.
Where It Fits in the Course
This is the classic, larger textbook on formal languages, automata and computability, and the most direct comparison is with Sipser's Introduction to the Theory of Computation, another clear upper-level introduction to automata, formal languages, computability and complexity. Either can serve as the main text. Kozen's Automata and Computability is a more compact alternative made of short chapters and goes further into topics such as Kleene algebra and Gödel's theorems, but stops before complexity.
Linz and Rodger's An Introduction to Formal Languages and Automata puts explanation and worked examples ahead of formalism and is a good companion for a student who wants more explanation. MacCormick's What Can Be Computed? approaches the same theory through Python programs, and Arora and Barak's Computational Complexity is the graduate-level continuation of Chapters 10 and 11.
How to Use This Book
Pearson's page does not state prerequisites; sets, relations, induction and proof are the sensible background, and programming experience helps with the practical motivation.
A practical plan:
- Core: Chapters 1–4 for regular languages, Chapters 5–6 for context-free grammars and pushdown automata, and Chapters 8–9 for Turing machines and undecidability.
- Lighter on a first pass: Chapters 4 and 7, the two "Properties" chapters, can be read lightly first and returned to when the proof techniques are familiar.
- Optional: Chapters 10 and 11 if the course includes complexity, otherwise a complexity text.
Work through the exercises, and for each model (finite automaton, grammar, pushdown automaton, Turing machine) write a small example by hand and convert it into the equivalent model that the book teaches next.