Book:John E. Hopcroft/Introduction to Automata Theory, Languages, and Computation/Third Edition
Jump to navigation
Jump to search
John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation (3rd Edition)
Published $\text {2006}$, Addison-Wesley
- ISBN 0-321-45536-3
Subject Matter
Contents
- 1 Automata: The Methods and the Madness
- 1.1 Why Study Automata Theory?
- 1.2 Introduction to Formal Proof
- 1.3 Additional Forms of Proof
- 1.4 Inductive Proofs
- 1.5 The Central Concepts of Automata Theory
- 1.6 Summary of Chapter 1
- 1.7 Gradience Problems for Chapter 1
- 1.8 References for Chapter 1
- 2 Finite Automata
- 2.1 An Informal Picture of Finite Automata
- 2.2 Deterministic Finite Automata
- 2.3 Nondeterministic Finite Automata
- 2.4 An Application: Text Search
- 2.5 Finite Automata With Epsilon-Transitions
- 2.6 Summary of Chapter 2
- 2.7 Gradience Problems for Chapter 2
- 2.8 References for Chapter 2
- 3 Regular Expressions and Languages
- 3.1 Regular Expressions
- 3.2 Finite Automata and Regular Expressions
- 3.3 Applications of Regular Expressions
- 3.4 Algebraic Laws for Regular Expressions
- 3.5 Summary of Chapter 3
- 3.6 Gradience Problems for Chapter 3
- 3.7 References for Chapter 3
- 4 Properties of Regular Languages
- 4.1 Proving Languages Not to Be Regular
- 4.2 Closure Properties of Regular Languages
- 4.3 Decision Properties of Regular Languages
- 4.4 Equivalence and Minimization of Automata
- 4.5 Summary of Chapter 4
- 4.6 Gradience Problems for Chapter 4
- 4.7 References for Chapter 4
- 5 Context-Free Grammars and Languages
- 5.1 Context-Free Grammars
- 5.2 Parse Trees
- 5.3 Applications of Context-Free Grammars
- 5.4 Ambiguity in Grammars and Languages
- 5.5 Summary of Chapter 5
- 5.6 Gradience Problems for Chapter 5
- 5.7 References for Chapter 5
- 6 Pushdown Automata
- 6.1 Definition of the Pushdown Automaton
- 6.2 The Languages of a PDA
- 6.3 Equivalence of PDA's and CFG's
- 6.4 Deterministic Pushdown Automata
- 6.5 Summary of Chapter 6
- 6.6 Gradience Problems for Chapter 6
- 6.7 References for Chapter 6
- 7 Properties of Context-Free Languages
- 7.1 Normal Forms for Context-Free Grammars
- 7.2 The Pumping Lemma for Context-Free Languages
- 7.3 Closure Properties of Context-Free Languages
- 7.4 Decision Properties of CFL's
- 7.5 Summary of Chapter 7
- 7.6 Gradience Problems for Chapter 7
- 7.7 References for Chapter 7
- 8 Introduction to Turing Machines
- 8.1 Problems That Computers Cannot Solve
- 8.2 The Turing Machine
- 8.3 Programming Techniques for Turing Machines
- 8.4 Extensions to the Basic Turing Machine
- 8.5 Restricted Turing Machines
- 8.6 Turing Machines and Computers
- 8.7 Summary of Chapter 7
- 8.8 Gradience Problems for Chapter 7
- 8.9 References for Chapter 7
- 9 Undecidability
- 9.1 A Language That Is Not Recursively Enumerable
- 9.2 An Undecidable Problem That Is RE
- 9.3 Undecidable Problems About Turing Machines
- 9.4 Post's Correspondence Problem
- 9.5 Other Undecidable Problems
- 9.6 Summary of Chapter 9
- 9.7 Gradience Problems for Chapter 9
- 9.8 References for Chapter 9
- 10 Intractable Problems
- 10.1 The Classes $\PP$ and $\NN\PP$
- 10.2 An NP-Complete Problem
- 10.3 A Restricted Satisfiability Problem
- 10.4 Additional NP-Complete Problems
- 10.5 Summary of Chapter 10
- 10.6 Gradience Problems for Chapter 10
- 10.7 References for Chapter 10
- 11 Additional Classes of Problems
- 11.1 Complements of Languages in $\NN \PP$
- 11.2 Problems Solvable in Polynomial Space
- 11.3 A Problem That Is Complete for $\PP \SS$
- 11.4 Language Classes Based on Randomization
- 11.5 The Complexity of Primality Testing
- 11.6 Summary of Chapter 11
- 11.7 Gradience Problems for Chapter 11
- 11.8 References for Chapter 11
- Index
Further Editions
- 1979: John E. Hopcroft and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation