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

Jump to navigation
Jump to search
## John E. Hopcroft and Jeffrey D. Ullman:

## 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**

## Further Editions

- 2000: John E. Hopcroft and Jeffrey D. Ullman:
*Introduction to Automata Theory, Languages, and Computation*(2nd ed.)

## Also see

## Source work progress

- 1979: John E. Hopcroft and Jeffrey D. Ullman:
*Introduction to Automata Theory, Languages, and Computation*... (previous) ... (next): Chapter $1$: Preliminaries: Exercises: $1.12$

- Not all exercises are covered.