Introduction to automata theory, languages and computation / John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman

Includes index

Table of Contents
Automata The Methods and the Madness
Why Study Automata Theory
Introduction to Finite Automata
Structural Representations
Automata and Complexity
Introduction to Formal Proof
Deductive Proofs
Reduction to De nitions
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
Summary of Chapter
Gradiance Problems for Chapter
References for Chapter
Finite Automata
An Informal Picture of Finite Automata
The Ground Rules
The Protocol
vii
viii TABLE OF CONTENTS
Enabling the Automata to Ignore Actions
The Entire System as an Automaton
Using the Product Automaton to Validate the Protocol
Deterministic Finite Automata
De nition 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
Nondeterministic Finite Automata
An Informal View of Nondeterministic Finite Automata
De nition 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
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
Finite Automata With Epsilon
Transitions
Uses of
Transitions
The Formal Notation for an
NFA
Epsilon
Closures
Extended Transitions and Languages for
NFA s
Eliminating
Transitions
Exercises for Section
Summary of Chapter
Gradiance Problems for Chapter
References for Chapter
Regular Expressions and Languages
Regular Expressions
The Operators of Regular Expressions
Building Regular Expressions
Precedence of Regular
Expression Operators
Exercises for Section
Finite Automata and Regular Expressions
From DFA s to Regular Expressions
Converting DFA s to Regular Expressions by Eliminating
States
TABLE OF CONTENTS ix
Converting Regular Expressions to Automata
Exercises for Section
Applications of Regular Expressions
Regular Expressions in UNIX
Lexical Analysis
Finding Patterns in Text
Exercises for Section
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
Summary of Chapter
Gradiance Problems for Chapter
References for Chapter
Properties of Regular Languages
Proving Languages Not to Be Regular
The Pumping Lemma for Regular Languages
Applications of the Pumping Lemma
Exercises for Section
Closure Properties of Regular Languages
Closure of Regular Languages Under Boolean Operations
Reversal
Homomorphisms
Inverse Homomorphisms
Exercises for Section
Decision Properties of Regular Languages
Converting Among Representations
Testing Emptiness of Regular Languages
Testing Membership in a Regular Language
Exercises for Section
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
Summary of Chapter
Gradiance Problems for Chapter
References for Chapter
x TABLE OF CONTENTS
Context Free Grammars and Languages
Context
Free Grammars
An Informal Example
De nition of Context
Free Grammars
Derivations Using a Grammar
Leftmost and Rightmost Derivations
The Language of a Grammar
Sentential Forms
Exercises for Section
Parse Trees
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
Applications of Context
Free Grammars
Parsers
The YACC Parser
Generator
Markup Languages
XML and Document
Type De nitions
Exercises for Section
Ambiguity in Grammars and Languages
Ambiguous Grammars
Removing Ambiguity From Grammars
Leftmost Derivations as a Way to Express Ambiguity
Inherent Ambiguity
Exercises for Section
Summary of Chapter
Gradiance Problems for Chapter
References for Chapter
Pushdown Automata
De nition of the Pushdown Automaton
Informal Introduction
The Formal De nition of Pushdown Automata
A Graphical Notation for PDA s
Instantaneous Descriptions of a PDA
Exercises for Section
The Languages of a PDA
Acceptance by Final State
Acceptance by Empty Stack
From Empty Stack to Final State
From Final State to Empty Stack
TABLE OF CONTENTS xi
Exercises for Section
Equivalence of PDA s and CFG s
From Grammars to Pushdown Automata
From PDA s to Grammars
Exercises for Section
Deterministic Pushdown Automata
De nition of a Deterministic PDA
Regular Languages and Deterministic PDA s
DPDA s and Context
Free Languages
DPDA s and Ambiguous Grammars
Exercises for Section
Summary of Chapter
Gradiance Problems for Chapter
References for Chapter
Properties of Context Free Languages
Normal Forms for Context
Free Grammars
Eliminating Useless Symbols
Computing the Generating and Reachable Symbols
Eliminating
Productions
Eliminating Unit Productions
Chomsky Normal Form
Exercises for Section
The Pumping Lemma for Context
Free Languages
The Size of Parse Trees
Statement of the Pumping Lemma
Applications of the Pumping Lemma for CFL s
Exercises for Section
Closure Properties of Context
Free Languages
Substitutions
Applications of the Substitution Theorem
Reversal
Intersection With a Regular Language
Inverse Homomorphism
Exercises for Section
Decision Properties of CFL s
Complexity of Converting Among CFG s and PDA s
Running Time of Conversion to Chomsky Normal Form
Testing Emptiness of CFL s
Testing Membership in a CFL
Preview of Undecidable CFL Problems
Exercises for Section
Summary of Chapter
Gradiance Problems for Chapter
References for Chapter
xii TABLE OF CONTENTS
Introduction to Turing Machines
Problems That Computers Cannot Solve
Programs that Print Hello World
The Hypothetical Hello World Tester
Reducing One Problem to Another
Exercises for Section
The Turing Machine
The Quest to Decide All Mathematical Questions
Notation for the Turing Machine
Instantaneous Descriptions for Turing Machines
Transition Diagrams for Turing Machines
The Language of a Turing Machine
Turing Machines and Halting
Exercises for Section
Programming Techniques for Turing Machines
Storage in the State
Multiple Tracks
Subroutines
Exercises for Section
Extensions to the Basic Turing Machine
Multitape Turing Machines
Equivalence of One
Tape and Multitape TM s
Running Time and the Many
Tapes
to
One Construction
Nondeterministic Turing Machines
Exercises for Section
Restricted Turing Machines
Turing Machines With Semi
in nite Tapes
Multistack Machines
Counter Machines
The Power of Counter Machines
Exercises for Section
Turing Machines and Computers
Simulating a Turing Machine by Computer
Simulating a Computer by a Turing Machine
Comparing the Running Times of Computers and Turing
Machines
Summary of Chapter
Gradiance Problems for Chapter
References for Chapter
Undecidability
A Language That Is Not Recursively Enumerable
Enumerating the Binary Strings
Codes for Turing Machines
The Diagonalization Language
TABLE OF CONTENTS xiii
Proof That Ld Is Not Recursively Enumerable
Exercises for Section
An Undecidable Problem That Is RE
Recursive Languages
Complements of Recursive and RE languages
The Universal Language
Undecidability of the Universal Language
Exercises for Section
Undecidable Problems About Turing Machines
Reductions
Turing Machines That Accept the Empty Language
Rice s Theorem and Properties of the RE Languages
Problems about Turing
Machine Speci cations
Exercises for Section
Post s Correspondence Problem
De nition of Post s Correspondence Problem
The Modi ed PCP
Completion of the Proof of PCP Undecidability
Exercises for Section
Other Undecidable Problems
Problems About Programs
Undecidability of Ambiguity for CFG s
The Complement of a List Language
Exercises for Section
Summary of Chapter
Gradiance Problems for Chapter
References for Chapter
Intractable Problems
The Classes P and NP
Problems Solvable in Polynomial Time
An Example Kruskal s Algorithm
Nondeterministic Polynomial Time
An NP Example The Traveling Salesman Problem
Polynomial
Time Reductions
NP
Complete Problems
Exercises for Section
An NP
Complete Problem
The Satis ability Problem
Representing SAT Instances
NP
Completeness of the SAT Problem
Exercises for Section
A Restricted Satis ability Problem
Normal Forms for Boolean Expressions
Converting Expressions to CNF
xiv TABLE OF CONTENTS
NP
Completeness of CSAT
NP
Completeness of SAT
Exercises for Section
Additional NP
Complete Problems
Describing NP
complete Problems
The Problem of Independent Sets
The Node
Cover Problem
The Directed Hamilton
Circuit Problem
Undirected Hamilton Circuits and the TSP
Summary of NP
Complete Problems
Exercises for Section
Summary of Chapter
Gradiance Problems for Chapter
References for Chapter
Additional Classes of Problems
Complements of Languages in NP
The Class of Languages Co
NP
NP
Complete Problems and Co
NP
Exercises for Section
Problems Solvable in Polynomial Space
Polynomial
Space Turing Machines
Relationship of PS and NPS to Previously De ned Classes
Deterministic and Nondeterministic Polynomial Space
A Problem That Is Complete for PS
PS
Completeness
Quanti ed Boolean Formulas
Evaluating Quanti ed Boolean Formulas
PS
Completeness of the QBF Problem
Exercises for Section
Language Classes Based on Randomization
Quicksort an Example of a Randomized Algorithm
A Turing
Machine Model Using Randomization
The Language of a Randomized Turing Machine
The Class RP
Recognizing Languages in RP
The Class ZPP
Relationship Between RP and ZPP
Relationships to the Classes P and NP
The Complexity of Primality Testing
The Importance of Testing Primality
Introduction to Modular Arithmetic
The Complexity of Modular
Arithmetic Computations
Random
Polynomial Primality Testing
Nondeterministic Primality Tests
TABLE OF CONTENTS xv
Exercises for Section
Summary of Chapter
Gradiance Problems for Chapter
References for Chapter
Index