自动机理论、语言和计算导论（第2版）（英文影印版） (2010 年度畅销榜NO.2173 )

本书是一本有关自动机理论、形式语言和计算复杂性的经典著作。第2版出版时，主要供研究生教学使用。由于自动机和语言理论在计算机科学的教育中已成为本科生的主要课程，作者在第2版的基础上作了全面修订。本书（第2版）除了继承原书“外看大，内看小”的特点外，在内容和风格上都作了很大的调整：降低了数学上的难度，删除了一些应用背景不大的内容，增加了一些在实践中较有影响的例子，把相关内容成功地纳入了本科阶段的教育体系。本书主要内容包括：有限状态自动机，正规语言，正规表达式，上下文无关文法，上下文无关语言，下推自动机，图灵机以及问题的不可解性、难解性和复杂性。每节后都附有练习。本书适合作计算机科学相关专业高年级教学用书。\r\n\r\n\r\n
\r\n

1 Automata: The Methods and the Madness \r\n\r\n 1.l Why Study Automata Theory? \r\n\r\n 1.1.1 Introduction to Finite Automata \r\n\r\n 1.1.2 Structural Representations \r\n\r\n 1.1.3 Automata and Complexity \r\n\r\n 1.2 Introduction to Formal Proof \r\n\r\n 1.2.1 Deductive Proofs \r\n\r\n 1.2.2 Reduction to Definitions \r\n\r\n 1.2.3 Other Theorem Forms \r\n\r\n 1.2.4 Theorems That Appear Not to Be If Then Statements \r\n\r\n 1.3 Additional Forms of Proof \r\n\r\n 1.3.1 Proving Equivalences About Sets \r\n\r\n 1.3.2 The Contrapositive \r\n\r\n 1.3.3 Proof by Contradiction \r\n\r\n 1.3.4 Counterexamples \r\n\r\n 1.4 Inductive Proofs \r\n\r\n 1.4.1 Inductions on Integers \r\n\r\n 1.4.2 More General Forms of Integer Inductions \r\n\r\n 1.4.3 Structural Inductions \r\n\r\n 1.4.4 Mutual Inductions \r\n\r\n 1.5 The Central Concepts of Aotomata Theory \r\n\r\n l.5.1 Alphabets \r\n\r\n 1.5.2 Strings \r\n\r\n 1.5.3 Languages \r\n\r\n 1.5.4 Problems \r\n\r\n 1.6 Summary of Chapter 1 \r\n\r\n 1.7 References for Chapter 1 \r\n\r\n \r\n\r\n 2 Finite Automata \r\n\r\n 2.1 An Informal Picture of Finite Automata \r\n\r\n 2.1.l The Ground Rules \r\n\r\n 2.1.2 The Protocol \r\n\r\n 2.1.3 Enabling the Automata to Ignore Actions \r\n\r\n 2.1.4 The Entire System as an Automaton \r\n\r\n 2.1.5 Using the Product Automaton to Validate the Protocol \r\n\r\n 2.2 Deterministic Finite Automata \r\n\r\n 2.2.1 Definition of a Deterministic Finite Automaton \r\n\r\n 2.2.2 How a DFA Processes Strings \r\n\r\n 2.2.3 Simpler Notations for DFA's \r\n\r\n 2.2.4 Extending the Transition Function to Strings \r\n\r\n 2.2.5 The Language of a DFA \r\n\r\n 2.2.6 Exercises for Section 2.2 \r\n\r\n 2.3 Nondeterministic Finite Automata \r\n\r\n 2.3.l An Informal View of Nondeterministic Finite Automata \r\n\r\n 2.3.2 Definition of Nondeterministic Finite Automata \r\n\r\n 2.3.3 The Extended Transition Function \r\n\r\n 2.3.4 The Language of an NFA \r\n\r\n 2.3.5 Equivalence of Deterministic and Nondeterministic Finite Automata \r\n\r\n 2.3.6 A Bad Case for the Subset Construction \r\n\r\n 2.3.7 Exercises for Section 2.3 \r\n\r\n 2.4 An Application: Text Search \r\n\r\n 2.4.1 Finding Strings in Text \r\n\r\n 2.4.2 Nondeterministic Finite Automata for Text Search \r\n\r\n 2.4.3 A DFA to Recognize a Set of Keywords \r\n\r\n 2.4.4 Exercises for Section 2.4 \r\n\r\n 2.5 Finite Automata With Epsilon-Transitions \r\n\r\n 2.5.1 Uses of e-Transitions \r\n\r\n 2.5.2 The Formal Notation for an e-NFA \r\n\r\n 2.5.3 Epsilon-Closures \r\n\r\n 2.5.4 Extended Transitions and Languages for E-NFA's \r\n\r\n 2.5.5 Eliminating e-Transitions \r\n\r\n 2.5.6 Exercises for Section 2.5 \r\n\r\n 2.6 Summary of Chapter 2 \r\n\r\n 2.7 References for Chapter 2 \r\n\r\n \r\n\r\n 3 Regular Expressions and Languages \r\n\r\n 3.1 Regular Expressions \r\n\r\n 3.1.1 The Operators of Regular Expressions \r\n\r\n 3.1.2 Building Regu1ar Expressions \r\n\r\n 3.l.3 Precedence of Regular-Expression Operators \r\n\r\n 3.1.4 Exercises for Section 3.1 \r\n\r\n 3.2 Finite Automata and Regu1ar Expressions \r\n\r\n 3.2.1 From DFA's to Regular Expressions \r\n\r\n 3.2.2 Converting DFA's to Regular Expressions by Eliminating States \r\n\r\n 3.2.3 Converting Regular Expressions to Automata \r\n\r\n 3.2.4 Exercises for Section 3.2 \r\n\r\n 3.3 Applications of Regular Expressions \r\n\r\n 3.3.1 Regular Expressions in UNIX \r\n\r\n 3.3.2 Lexical Ana1ysis \r\n\r\n 3.3.3 Finding Patterns in Text \r\n\r\n 3.3.4 Exercises for Section 3.3 \r\n\r\n 3.4 Algebraic Laws for Regular Expressions \r\n\r\n 3.4.1 Associativity and Commutativity \r\n\r\n 3.4.2 Identities and Annihilators \r\n\r\n 3.4.3 Distributive Laws \r\n\r\n 3.4.4 The Idempotent Law \r\n\r\n 3.4.5 Laws Involving Closures \r\n\r\n 3.4.6 Discovering Laws for Regular Expressions \r\n\r\n 3.4.7 The Test for a Regular-Expression Algebraic Law \r\n\r\n 3.4.8 Exercises for Section 3.4 \r\n\r\n 3.5 Summary of Chapter 3 \r\n\r\n 3.6 References for Chapter 3 \r\n\r\n \r\n\r\n 4 Properties of Regular Languages \r\n\r\n 4.1 Proving Languages not to be Regular \r\n\r\n 4.1.1 The Pumping Lemma for Regular Languages \r\n\r\n 4.1.2 Applications of the Pumping Lemma \r\n\r\n 4.1.3 Exercises for Section 4.1 \r\n\r\n 4.2 Closure Properties of Regular Languages \r\n\r\n 4.2.l Closure of Regular Languages Under Boolean Operations \r\n\r\n 4.2.2 Reversal \r\n\r\n 4.2.3 Homomorphisms \r\n\r\n 4.2.4 Inverse Homomorphisms \r\n\r\n 4.2.5 Exercises for Section 4.2 \r\n\r\n 4.3 Decision Properties of Regular Languages \r\n\r\n 4.3.1 Converting Among Representations \r\n\r\n 4.3.2 Testing Emptiness of Regular Languages \r\n\r\n 4.3.3 Testing Membership in a Regular Language \r\n\r\n 4.3.4 Exercises for Section 4.3 \r\n\r\n 4.4 Equivalence and Minimization of Automata - \r\n\r\n 4.4.1 Testing Equivalence of States \r\n\r\n 4.4.2 Testing Equivalence of Regular Languages \r\n\r\n 4.4.3 Minimization of DFA's \r\n\r\n 4.4.4 Why the Minimized DFA Can't Be Beaten \r\n\r\n 4.4.5 Exercises for Section 4.4 \r\n\r\n 4.5 Summary Of Chapter 4 \r\n\r\n 4.6 References for Chapter 4 \r\n\r\n \r\n\r\n 5 Context-nee Grammars and Languages \r\n\r\n 5.1 Context-Free Grammars \r\n\r\n 5.1.1 An Informal Example \r\n\r\n 5.1.2 Definition Of Context-nee Grammars \r\n\r\n 5.1.3 Derivations Using a Grammar \r\n\r\n 5.1.4 Leftmost and Rightmost Derivations \r\n\r\n 5.1.5 The Language of a Grammar \r\n\r\n 5.1.6 Sentential Forms \r\n\r\n 5.1.7 Exercises for Section 5.1 \r\n\r\n 5.2 Parse Trees \r\n\r\n 5.2.1 Constructing Parse Trees \r\n\r\n 5.2.2 The Yield of a Parse Tree \r\n\r\n 5.2.3 Inference, Derivations, and Parse Trees \r\n\r\n 5.2.4 From Inferences to Trees \r\n\r\n 5.2.5 From Trees to Derivations \r\n\r\n 5.2.6 Mom Derivations to Recursive Inferences \r\n\r\n 5.2.7 Exercises for Section 5.2 \r\n\r\n 5.3 Applications of Context-Tree Grammars \r\n\r\n 5.3.1 Parsers \r\n\r\n 5.3.2 The YACC Parser-Generator \r\n\r\n 5.3.3 Markup Languages \r\n\r\n 5.3.4 XML and Document-Type Definitions \r\n\r\n 5.3.5 Exercises for Section 5.3 \r\n\r\n 5.4 Ambiguity in Grammars and Languages \r\n\r\n 5.4.1 Ambiguous Grammars \r\n\r\n 5.4.2 Removing Ambiguity nom Grammars \r\n\r\n 5.4.3 Leftmost Derivations as a Way to Express Ambiguity \r\n\r\n 5.4.4 Inherent Ambiguity \r\n\r\n 5.4.5 Exercises for Section 5.4 \r\n\r\n 5.5 Summary of Chapter 5 \r\n\r\n 5.6 References for Chapter 5 \r\n\r\n \r\n\r\n 6 Pushdown Automata \r\n\r\n 6.1 Definition of the Pushdown Automaton \r\n\r\n 6.1.1 Informal Introduction \r\n\r\n 6.1.2 The Formal Definition Of Pushdown Automata \r\n\r\n 6.1.3 A Graphical Notation for PDA's \r\n\r\n 6.1.4 Instantaneous Descriptions Of a PDA \r\n\r\n 6.1.5 Exercises for Section 6.1 \r\n\r\n 6.2 The Languages of a PDA \r\n\r\n 6.2.1 Acceptance by Final State \r\n\r\n 6.2.2 Acceptance by Empty Stack \r\n\r\n 6.2.3 From Empty Stack to Final State \r\n\r\n 6.2.4 From Final State to Empty Stack \r\n\r\n 6.2.5 Excises for Section 6.2 \r\n\r\n 6.3 Equivalence of PDA's and CFG's \r\n\r\n 6.3.1 From Grammars to Pushdown Automata \r\n\r\n 6.3.2 From PDA's to Grammars \r\n\r\n 6.3.3 Exercises for Section 6.3 \r\n\r\n 6.4 Deterministic Pushdown Automata \r\n\r\n 6.4.l Definition of a Deterministic PDA \r\n\r\n 6.4.2 Regular Languages and Deterministic PDA's \r\n\r\n 6.4.3 DPDA's and Context-Free Languages \r\n\r\n 6.4.4 DPDA's and Ambiguous Grammars \r\n\r\n 6.4.5 Exercises for Section 6.4 \r\n\r\n 6.5 Summary of Chapter 6 \r\n\r\n 6.6 References for Chapter 6 \r\n\r\n \r\n\r\n 7 Properties of Context-Free Languages \r\n\r\n 7.1 Normal Forms for Context--Free Grammars \r\n\r\n 7.l.l Eliminating Useless Symbols \r\n\r\n 7.1.2 Computing the Generating and Reachable Symbols \r\n\r\n 7.1.3 Eliminating e-Productions \r\n\r\n 7.1.4 Eliminating Unit Productions \r\n\r\n 7.l.5 Chomsky Normal Form \r\n\r\n 7.1.6 Exercises for Section 7.1 \r\n\r\n 7.2 The Pumping Lemma for Context-Free Languages \r\n\r\n 7.2.l The Size of Parse Trees \r\n\r\n 7.2.2 Statement of the Pumping Lemma \r\n\r\n 7.2.3 Applications of the Pumping Lemma for CFL's \r\n\r\n 7.2.4 Exercises for Section 7.2 \r\n\r\n 7.3 Closure Properties of Context-Free Languages \r\n\r\n 7.3.1 Substitutions \r\n\r\n 7.3.2 Applications of the Substitution Theorem \r\n\r\n 7.3.3 Reversal \r\n\r\n 7.3.4 Intersection With a Regular Language \r\n\r\n 7.3.5 Inverse Homomorphism \r\n\r\n 7.3.6 Exercises for Section 7.3 \r\n\r\n 7.4 Decision Properties of CFL's \r\n\r\n 7.4.1 Complexity of Converting Among CFG's and PDA's \r\n\r\n 7.4.2 Running Time of Conversion to Chomsky Normal Form \r\n\r\n 7.4.3 Testing Emptiness of CFL's \r\n\r\n 7.4.4 Testing Membership in a CFL \r\n\r\n 7.4.5 Preview of Undecidable CFL Problems \r\n\r\n 7.4.6 Exercises for Section 7.4 \r\n\r\n 7.5 Summary of Chapter 7 \r\n\r\n 7.6 References for Chapter 7 \r\n\r\n \r\n\r\n 8 Introduction to Turing Machines \r\n\r\n 8.1 Problems That Computers Cannot Solve \r\n\r\n 8.1.1 Programs that Print 'Hello, World' \r\n\r\n 8.1.2 The Hypothetical 'Hello, World' Tester \r\n\r\n 8.1.3 Reducing One Problem to Another \r\n\r\n 8.1.4 Exercises for Section 8.1 \r\n\r\n 8.2 The Turing Machine \r\n\r\n 8.2.1 The Quest to Decide All Mathematical Questions \r\n\r\n 8.2.2 Notation for the Turing Machine \r\n\r\n 8.2.3 Instantaneous Descriptions for Turing Machines \r\n\r\n 8.2.4 Thansition Diagrams for Turing Machines \r\n\r\n 8.2.5 The Language of a Turing Machine \r\n\r\n 8.2.6 Turing Machines and Halting \r\n\r\n 8.2.7 Exercises for Section 8.2 \r\n\r\n 8.3 Programming Techniques for Turing Machines \r\n\r\n 8.3.l Storage in the State \r\n\r\n 8.3.2 Multiple Thacks \r\n\r\n 8.3.3 Subroutines \r\n\r\n 8.3.4 Exercises for Section 8.3 \r\n\r\n 8.4 Extensions to the Basic Turing Machine \r\n\r\n 8.4.l Multitape Turing Machines \r\n\r\n 8.4.2 Equivalence of One--Tape and Multitape TM's \r\n\r\n 8.4.3 Running Time and the Many-Tapes-to-One Construction \r\n\r\n 8.4.4 Nondeterministic Turing Machines \r\n\r\n 8.4.5 Exercises for Section 8.4 \r\n\r\n 8.5 Restricted Turing Machines \r\n\r\n 8.5.1 Turing Machines With Semi-infinite Tapes \r\n\r\n 8.5.2 Multistack Machines \r\n\r\n 8.5.3 Counter Machines \r\n\r\n 8.5.4 The Power of Counter Machines \r\n\r\n 8.5.5 Exercises for Section 8.5 \r\n\r\n 8.6 Turing Machines and Computers \r\n\r\n 8.6.1 Simulating a Turing Machine by Computer \r\n\r\n 8.6.2 Simulating a Computer by a Turing Machine \r\n\r\n 8.6.3 Comparing the Running Times of Computers and Turing Machines \r\n\r\n 8.7 Summary of Chapter 8 \r\n\r\n 8.8 References for Chapter 8 \r\n\r\n \r\n\r\n 9 Uudecidability \r\n\r\n 9.1 A Language That Is Not Recursively Enumerable \r\n\r\n 9.1.1 Enumerating the Binary Strings \r\n\r\n 9.1.2 Codes for Turing Machines \r\n\r\n 9.1.3 The Diagonalization Language \r\n\r\n 9.1.4 Proof that Ld is not Recursively Enumerable \r\n\r\n 9.1.5 Exercises for Section 9.1 \r\n\r\n 9.2 An Undecidable Problem That is RE \r\n\r\n 9.2.l Recursive Languages \r\n\r\n 9.2.2 Complements of Recursive and RE language \r\n\r\n 9.2.3 The Universal Language \r\n\r\n 9.2.4 Undecidability of the Universal Language \r\n\r\n 9.2.5 Exercises for Section 9.2 \r\n\r\n 9.3 Undecidable Problems About Turing Machines \r\n\r\n 9.3.1 Reductions \r\n\r\n 9.3.2 Turing Machines That Accept the Empty Language \r\n\r\n 9.3.3 Rice's Theorem and Properties of the RE Languages \r\n\r\n 9.3.4 Problems about Turing-Machine Specifications \r\n\r\n 9.3.5 Exercises for' Section 9.3 \r\n\r\n 9.4 Post's Correspondence Problem \r\n\r\n 9.4.l Definition of Post's Correspondence Problem \r\n\r\n 9.4.2 The 'Modified' PCP \r\n\r\n 9.4.3 Completion of the Proof of PCP Undecidability \r\n\r\n 9.4.4 Exercises for Section 9.4 \r\n\r\n 9.5 Other Undecidable Problems \r\n\r\n 9.5.1 Problems About Programs \r\n\r\n 9.5.2 Undecidability of Ambiguity for CFG's \r\n\r\n 9.5.3 The Complement of a List Language \r\n\r\n 9.5.4 Exercises for Section 9.5 \r\n\r\n 9.6 Summary of Chapter 9 \r\n\r\n 9.7 References for Chapter 9 \r\n\r\n \r\n\r\n 1O Intractable Problems \r\n\r\n 10.1 The Classes P and NP \r\n\r\n 10.l.1 Problems Solvable in Polynomial Time \r\n\r\n 10.1.2 An Example: Kruskal's Algorithm \r\n\r\n 10.1.3 Nondeterministic Polynomial Time \r\n\r\n 10.1.4 An NP Example: The Traveling Salesman Problem \r\n\r\n 10.l.5 Polynomial-Time Reductions \r\n\r\n 10.1.6 NP-Complete Problems \r\n\r\n 10.l.7 Exercises for Section 10.l \r\n\r\n l0.2 An NP-Complete Problem \r\n\r\n 10.2.1 The Satisfiability Problem \r\n\r\n 10.2.2 Representing SAT Instances \r\n\r\n 10.2.3 NP-Completeness of the SAT Problem \r\n\r\n 10.2.4 Exercises for Section 10.2 \r\n\r\n 10.3 A Restricted Satisfiability Problem \r\n\r\n 10.3.l Normal Forms for Boolean Expressions \r\n\r\n 10.3.2 Converting Expressions to CNF \r\n\r\n 10.3.3 NP-Completeness of CSAT \r\n\r\n l0.3.4 NP--Completeness of 3SAT \r\n\r\n 10.3.5 Exercises for Section 10.3 \r\n\r\n 10.4 Additional NP-Complete Problems \r\n\r\n 10.4.1 Describing NP-complete Problems \r\n\r\n 10.4.2 The Problem of Independent Sets \r\n\r\n 10.4.3 The Node-Cover Problem \r\n\r\n 10.4.4 The Directed Hamilton-Circuit Problem \r\n\r\n 10.4.5 Undirected Hamilton Circuits and the TSP \r\n\r\n 10.4.6 Summary of NP-Complete Problems \r\n\r\n 10.4.7 Exercises for Section 10.4 \r\n\r\n 10.5 Summary of Chapter 10 \r\n\r\n 10.6 References for Chapter 10 \r\n\r\n \r\n\r\n 11 Additional Classes of Problems \r\n\r\n 11.1 Complements of Languages in NP \r\n\r\n 11.1.1 The Class of Languages Co-NP \r\n\r\n 11.1.2 NP-Complete Problems and Co-NP \r\n\r\n 11.1.3 Exercises for Section 11.1 \r\n\r\n 11.2 Problems Solvable in Polynomial Space \r\n\r\n 11.2.1 Polynomial-Space Turing Machines \r\n\r\n 11.2.2 Relationship of PS and MS to Previously Defined Classes \r\n\r\n 11.2.3 Deterministic and Nondeterministic Polynomial Space \r\n\r\n 11.3 A Problem That Is Complete for PS \r\n\r\n 11.3.1 PS-Completeness \r\n\r\n 11.3.2 Quantified Boolean Formulas \r\n\r\n 11.3.3 Evaluating Quantified Boolean Formulas \r\n\r\n 11.3.4 PS-Completeness of the QBF Problem \r\n\r\n 11.3.5 Exercises for Section 11.3 \r\n\r\n 11.4 Language Classes Based on Randomization \r\n\r\n 11.4.1 Quicksort: an Example of a Randomized Algorithm \r\n\r\n 11.4.2 A Turing-Machine Model Using Randomization \r\n\r\n 11.4.3 The Language of a Randomized Turing Machine \r\n\r\n 11.4.4 The Class RP \r\n\r\n 11.4.5 Recognizing Languages in RP \r\n\r\n 11.4.6 The Class ZPP \r\n\r\n 11.4.7 Relationship Between RP and ZPP \r\n\r\n 11.4.8 Relationships to the Classes P and NP \r\n\r\n 11.5 The Complexity of Primality Testing \r\n\r\n 11.5.1 The Importance of Testing Primality \r\n\r\n 11.5.2 Introduction to Modular Arithmetic \r\n\r\n 11.5.3 The Complexity Of Modular-Arithmetic Computations \r\n\r\n 11.5.4 Random-Polynomial Primality Testing \r\n\r\n 11.5.5 Nondeterministic Primality Tests \r\n\r\n 11.5.6 Exercises for Section 11.5. \r\n\r\n 11.6 Summary of Chapter 11 \r\n\r\n 11.7 References for Chapter 11 \r\n
\r\n

In the preface from the 1979 predecessor to this book, Hopcroft and Ullman marveled at the fact that the subject of automata had exploded, compared with its state at the time they wrote their first book, in 1969. Truly, the 1979 book contained many topics not found in the earlier work and was about twice its size. If you compare this book with the 1979 book, you will find that, like the automobiles of the 1970's, this book is "larger on the outside, but smaller on the inside." That sounds like a retrograde step, but we axe happy with the changes for several reasons.

First, in 1979, automata and language theory was still an area of active research. A purpose of that book was to encourage mathematically inclined students to make new contributions to the field. Today there is little direct research in automata theory (as opposed to its applications), and thus little motivation for us to retain the succinct, highly mathematical tone of the 1979 book.

Second, the role of automata and language theory has changed over the past two decades. In 1979, automata was largely a graduate-level subject, and we imagined our reader was an advanced graduate student, especially those using the later chapters of the book. Today, the subject is a staple of the undergraduate curriculum. As such, the content of the book must assume less in the way of prerequisites from the student, and therefore must provide more of the background and details of arguments than did the earlier book.

A third change in the environment is that Computer Science has grown to an almost unimaginable degree in the past two decades. While in l979 it was often a challenge to fill up a curriculum with material that we felt would survive the next wave of technology, today very many subdisciplil1es compete for the limited amount of space in the undergraduate curriculum.

Fourthly, CS has become a more vocational subject, and there is a severe pragmatism among many of its students. We continue to be1ieve that aspects of automata theory axe essential tools in a variety of new disciplines, and we believe that the theoretical, mind-expanding exercises embodied in the typical automata course retain their value, no matter how much the student prefers to learn only the most immediately monetizable technology However, to assure a continued place for the subject on the menu of topics available to the computer science student, we believe it is necessary to emphasize the applications along with the mathematics. Thus, we have replaced a number of the more abstruse topics in the earlier book with examples of how the ideas are used today. While applications of automata and language theory to compilers are now so well understood that they are normally covered in a compiler course, there are a variety of more recent uses, including model-checking algorithms to verify protocols and document-description languages that are patterned on context-free grammars.

A final explanation for the simultaneous growth and shrinkage of the book is that we were today able to take advantage of the TEX and LATEX typesetting systems developed by Don Knuth and Les Lamport. The latter, especially, encourages the "open" style of typesetting that makes books larger, but easier to read. We appreciate the efforts of both men.

Use of the Book

This book is suitable for a quarter or semester course at the Junior level or above. At Stanford, we have used the notes in CS154, the course in automata and language theory It is a one-quarter course, which both Rajeev and Jeff have taught. Because of the limited time available, Chapter 11 is not covered, and some of the later material, such as the more difficult polynomial-time reductions in Section 10.4 are omitted as well. The book's Web site (see below) includes notes and syllabi for several offerings of CS154.

Some years ago, we found that many graduate students came to Stanford with a course in automata theory that did not include the theory of intractability. As the Stanford faculty believes that these ideas are essential for every computer scientist to know at more than the level of "NP-complete means it takes too long," there is another course, CS154N, that students may take to cove only Chapters 8, 9, and 10. They actually participate in roughly the last third of CS154 to fulfill the CS154N requirement. Even today, we find several students each quarter availing themselves of this option. Since it requires little extra effort, we recommend the approach.

Prerequisites

To make best use of this book, students should have taken previously a course covering discrete mathematics, e.g., graphs, trees, logic, and proof techniques. We assume also th8t they have had several courses in programming, and are familiar with common data structures, recursion, and the role of major system components such as compilers. These prerequisites should be obtained in a typical freshman-sophomore CS program.

Exercises

The book contains extensive exercises, with some for almost every section. We indicate harder exercises or parts of exercises with an exclamation point. The hardest exercises have a double exclamation point.

Some of the exercises or parts axe marked with a star. For these exercises, we shall endeavor to maintain solutions accessible through the book's Web page. These solutions are publicly available and should be used for self testing. Note that in a few cases, one exercise B asks for modification or adaptation of your solution to another exercise A. If certain parts of A have solutions, then you should expect the corresponding parts of B to have solutions as well.

Support on the world Wide Web

The book's home page is http: //www-db. stanford. edu/~ul1man/ia1c. html Here are solutions to starred exercises, errata as we learn of them, and backup materials. We hope to make available the notes for each offering of CS154 as we learn it, including homeworks, solutions, and exams.

Acknowledgements

A handout on "how to do proofs" by Craig Silverstein influenced some of the material in Chapter 1. Comments and errata on drafts of this book were received from: Zoe Abrams, George Candea, Haowen Chen, Byong-Gun Chun, Jeffrey Shallit, Bret Taylor, Jason Townsend, and Erik Uzureau. They are gratefully acknowledged. Remaining errors are ours,of course.

J. E. H.

R. M.

J. D. U.

Ithaca NY and Stanford CA

September, 2000