Table of contents for Introduction to automata theory, languages, and computation / by John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman.

Bibliographic record and links to related information available from the Library of Congress catalog.

Note: Contents data are machine generated based on pre-publication provided by the publisher. Contents may have variations from the printed book or be incomplete or contain other coding.


Counter
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 

Library of Congress Subject Headings for this publication:

Machine theory.
Formal languages.
Computational complexity.