Book:John E. Hopcroft/Introduction to Automata Theory, Languages, and Computation

From ProofWiki
Jump to navigation Jump to search

John E. Hopcroft and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation

Published $\text {1979}$, Addison-Wesley

ISBN 0-201-02988-X


Affectionately known as "The Cinderella Book".


Subject Matter


Contents

Preface
Chapter 1 Preliminaries
1.1 Strings, alphabets and languages
1.2 Graphs and trees
1.3 Inductive proofs
1.4 Set notation
1.5 Relations
1.6 Synopsis of the book
Chapter 2 Finite Automata and Regular Expressions
2.1 Finite state systems
2.2 Basic definitions
2.3 Nondeterministic finite automata
2.4 Finite automata with $\epsilon$-moves
2.5 Regular expressions
2.6 Two-way finite automata
2.7 Finite automata with output
2.8 Applications of finite automata
Chapter 3 Properties of Regular Sets
3.1 The pumping lemma for regular sets
3.2 Closure properties of regular sets
3.3 Decision algorithms for regular sets
3.4 The Myhill-Nerode theorem and minimization of finite automata
Chapter 4 Context-Free Grammars
4.1 Motivation and introduction
4.2 Context-free grammars
4.3 Derivation trees
4.4 Simplification of context-free grammars
4.5 Chomsky's normal form
4.6 Greibach normal form
4.7 The existence of inherently ambiguous context-free languages
Chapter 5 Pushdown Automata
5.1 Informal description
5.2 Definitions
5.3 Pushdown automata and context-free languages
Chapter 6 Properties of Context-Free Languages
6.1 The pumping lemma for CFL's
6.2 Closure properties of CFL's
6.3 Decision algorithms for CFL's
Chapter 7 Turing Machines
7.1 Introduction
7.2 The Turing machine model
7.3 Computable languages and functions
7.4 Techniques for Turing machine construction
7.5 Modifications of Turing machines
7.6 Church's hypothesis
7.7 Turing machines as enumerators
7.8 Restricted Turing machines equivalent to the basic model
Chapter 8 Undecidability
8.1 Problems
8.2 Properties of recursive and recursively enumerable languages
8.3 Universal Turing machines and an undecidable problem
8.4 Rice's theorem and some more undecidable problems
8.5 Undecidability of Post's correspondence problem
8.6 Valid and invalid computations of TM's: a tool for proving CFL problems undecidable
8.7 Greibach's theorem
8.8 Introduction to recursive function theory
8.9 Oracle computations
Chapter 9 The Chomsky Hierarchy
9.1 Regular grammars
9.2 Unrestricted grammars
9.3 Context-sensitive languages
9.4 Relations between classes of languages
Chapter 10 Deterministic Context-Free Languages
10.1 Normal forms for DPDA's
10.2 Closure of DCFL's under complementation
10.3 Predicting machines
10.4 Additional closure properties of DCFL's
10.5 Decision properties of DCFL's
10.6 $\map {LR} 0$ grammars
10.7 $\map {LR} 0$ grammars and DPDA's
10.8 $\map {LR} k$ grammars
Chapter 11 Closure Properties of Families of Languages
11.1 Trios and full trios
11.2 Generalized sequential machine mappings
11.3 Other closure properties of trios
11.4 Abstract families of languages
11.5 Independence of the AFL operations
11.6 Summary
Chapter 12 Computational Complexity Theory
12.1 Definitions
12.2 Linear speed-ups, tape compression and reductions in the number of tapes
12.3 Hierarchy theorems
12.4 Relations among complexity measures
12.5 Translation lemmas and nondeterministic hierarchies
12.6 Properties of general complexity measures: the gap, speedup, and union theorems
12.7 Axiomatic complexity theory
Chapter 13 Intractable Problems
13.1 Polynomial time and space
13.2 Some $NP$-complete problems
13.3 The class co-$\mathscr {NP}$
13.4 PSPACE-complete problems
13.5 Complete problems for $\mathscr P$ and $\map {\mathrm {NSPACE} } {\log n}$
13.6 Some provably intractable problems
13.7 The $\mathscr P = \mathscr {NP}$ question with Turing machines with oracles:
limits on our ability to tell whether $\mathscr P = \mathscr {NP}$
Chapter 14 Highlights of Other Important Language Classes
14.1 Auxiliary pushdown automata
14.2 Stack automata
14.3 Indexed languages
14.4 Developmental systems
Bibliography
Index


Next


Further Editions


Also see


Source work progress

Not all exercises are covered.
Retrieved from "https://proofwiki.org/w/index.php?title=Book:John_E._Hopcroft/Introduction_to_Automata_Theory,_Languages,_and_Computation&oldid=614627"