Introduction to Automata Theory, Languages, and Computation, 2/E
John E. Hopcroft, Cornell UniversityRajeev Motwani, Stanford University
Jeffrey D. Ullman, Stanford University
ISBN-10: 0201441241
ISBN-13: 9780201441246
Publisher: Addison-Wesley
Copyright: 2001
Format: Cloth; 521 pp
Published: 11/14/2000
Table of Contents
2. Finite Automata.
3. Regular Expressions and Languages.
4. Properties of Regular Languages.
5. Context-Free Grammars and Languages.
(NOTE: Each chapter concludes with Summary and References.)
1. Automata: The Methods and the Madness.
Why Study Automata Theory?
Introduction to Finite Automata.
Structural Representations.
Automata and Complexity.
Introduction to Formal Proof.
Deduction Proofs.
Reduction to Definitions.
Other Theorem Forms.
Theorems That Appear Not to Be If-Then Statements.
Additional Forms of Proof.
Proving Equivalences About Sets
The Contrapositive.
Proof by Contradiction.
Counterexamples.
Inductive Proofs.
Inductions on Integers.
More General Forms of Integer Inductions.
Structural Inductions.
Mutual Inductions.
The Central Concepts of Automata Theory
Alphabets.
Strings.
Languages.
Problems.
2. Finite Automata.
An Informal Picture of Finite Automata.
The Ground Rules.
The Protocol.
Enabling the Automata to Ignore Actions.
The Entire System as an Automaton.
Using the Product Automaton to Validate the Protocol.
Deterministic Finite Automata.
Definition of a Deterministic Finite Automaton.
How a DFA Processes Strings.
Simpler Notations for DFA's.
Extending the Transition Function to Strings.
The Language of a DFA
Exercises for Section 2.2.
Nondeterministic Finite Automata.
An Informal View of Nondeterministic Finite Automata.
Definition of Nondeterministic Finite Automata.
The Extended Transition Function.
The Language of an NFA.
Equivalence of Deterministic and Nondeterministic Finite Automata.
A Bad Case for the Subset Construction.
Exercises for Section 2.3.
An Application: Text Search.
Finding Strings in Text.
Nondeterministic Finite Automata for Text Search.
A DFA to Recognize a Set of Keywords.
Exercises for Section 2.4.
Finite Automata with Epsilon-Transitions.
Uses of e-Transitions.
The Formal Notation for an e-NFA.
Epsilon-Closures.
Extended Transitions and Languages for e-NFA's.
Eliminating e-Transitions.
3. Regular Expressions and Languages.
Regular Expressions.
The Operators of Regular Expressions.
Building Regular Expressions.
Precedence of Regular-Expression Operators.
Finite Automata and Regular Expressions.
From DFA's to Regular Expressions.
Converting DFA's to Regular Expressions by Eliminating States.
Converting Regular Expressions to Automata.
Exercises for Section 3.2.
Applications of Regular Expressions.
Regular Expressions in UNIX.
Lexical Analysis.
Finding Patterns in Text.
Exercises for Section 3.3.
Algebraic Laws for Regular Expressions.
Associativity and Commutativity.
Identities and Annihilators.
Distributive Laws.
The Idempotent Law.
Laws Involving Closures.
Discovering Laws for Regular Expressions.
The Test for a Regular-Expression Algebraic Law.
Exercises for Section 3.4.
4. Properties of Regular Languages.
Proving Languages not to be Regular.
The Pumping Lemma for Regular Languages.
Applications of the Pumping Lemma.
Exercises for Section 4.1.
Closure Properties of Regular Languages.
Closure of Regular Languages Under Boolean Operations.
Reversal.
Homomorphisms.
Inverse Homomorphisms.
Exercises for Section 4.2.
Decision Properties of Regular Languages.
Converting Among Representations.
Testing Emptiness of Regular Languages.
Testing Membership in a Regular Language.
Exercises for Section 4.3.
Equivalence and Minimization of Automata.
Testing Equivalence of States.
Testing Equivalence of Regular Languages.
Minimization of DFA's.
Why the Minimized DFA Can't Be Beaten.
Exercises for Section 4.4.
5. Context-Free Grammars and Languages.
Context-Free Grammars.
An Informal Example.
Definition of Context-Free Grammars.
Derivations Using a Grammar.
Leftmost and Rightmost Derivations.
The Language of a Grammar.
Sentential Forms.
Exercises for Section 5.1.
Parse Tress.
Constructing Parse Trees.
The Yield of a Parse Tree.
Inference, Derivations, and Parse Trees.
From Inferences to Trees.
From Trees to Derivations.
From Derivations to Recursive Inferences.
Exercises for Section 5.2.
Applications of Context-Free Grammars.
Parsers.
The YACC Parser-Generator.Markup Languages.
XML and Documen...
.:: Home ::.
