形式语言与自动机导论 英文版 第3版PDF电子书下载

Chapter 1 Introduction to the Theory of Computation 1

1.1 Mathematical Preliminaries and Notation 3

Sets 3

Functions and Relations 5

Graphs and Trees 7

Proof Techniques 9

1.2 Three Basic Concepts 15

Languages 15

Grammars 19

Automata 25

1.3 Some Applications 29

Chapter 2 Finite Automata 35

2.1 Deterministic Finite Accepters 36

Deterministic Accepters and Transition Graphs 36

Languages and Dfas 38

Regular Languages 42

2.2 Nondeterministic Finite Accepters 47

Definition of a Nondeterministic Accepter 48

Why Nondeterminism? 52

2.3 Equivalence of Deterministic and Nondeterministic Finite Accepters 55

2.4 Reduction of the Number of States in Finite Automata 62

Chapter 3 Regular Languages and Regular Grammars 71

3.1 Regular Expressions 71

Formal Definition of a Regular Expression 72

Languages Associated with Regular Expressions 73

3.2 Connection Between Regular Expressions and Regular Languages 78

Regular Expressions Denote Regular Languages 78

Regular Expressions for Regular Languages 81

Regular Expressions for Describing Simple Patterns 85

3.3 Regular Grammars 89

Right-and Left-Linear Grammars 89

Right-Linear Grammars Generate Regular Languages 91

Right-Linear Grammars for Regular Languages 93

Equivalence Between Regular Languages and Regular Grammars 95

Chapter 4 Properties of Regular Languages 99

4.1 Closure Properties of Regular Languages 100

Closure under Simple Set Operations 100

Closure under Other Operations 103

4.2 Elementary Questions about Regular Languages 111

4.3 Identifying Nonregular Languages 114

Using the Pigeonhole Principle 114

A Pumping Lemma 115

Chapter 5 Context-Free Languages 125

5.1 Context-Free Grammars 126

Examples of Context-Free Languages 127

Leftmost and Rightmost Derivations 129

Derivation Trees 130

Relation Between Sentential Forms and Derivation Trees 132

5.2 Parsing and Ambiguity 136

Parsing and Membership 136

Ambiguity in Grammars and Languages 141

5.3 Context-Free Grammars and Programming Languages 146

Chapter 6 Simplification of Context-Free Grammars 149

6.1 Methods for Transforming Grammars 150

A Useful Substitution Rule 150

Removing Useless Productions 152

Removing λ-Productions 156

Removing Unit-Productions 158

6.2 Two Important Normal Forms 165

Chomsky Normal Form 165

Greibach Normal Form 168

6.3 A Membership Algorithm for Context-Free Grammars 172

Chapter 7 Pushdown Automata 175

7.1 Nondeterministic Pushdown Automata 176

Definition of a Pushdown Automaton 176

A Language Accepted by a Pushdown Automaton 179

7.2 Pushdown Automata and Context-Free Languages 184

Pushdown Automata for Context-Free Languages 184

Context-Free Grammars for Pushdown Automata 189

7.3 Deterministic Pushdown Automata and Deterministic Context-Free Languages 195

7.4 Grammars for Deterministic Context-Free Languages 200

Chapter 8 Properties of Context-Free Languages 205

8.1 Two Pumping Lemmas 206

A Pumping Lemma for Context-Free Languages 206

A Pumping Lemma for Linear Languages 210

8.2 Closure Properties and Decision Algorithms for Context-Free Languages 213

Closure of Context-Free Languages 213

Some Decidable Properties of Context-Free Languages 218

Chapter 9 Turing Machines 221

9.1 The Standard Turing Machine 222

Definition of a Turing Machine 222

Turing Machines as Language Accepters 229

Turing Machines as Transducers 232

9.2 Combining Turing Machines for Complicated Tasks 238

9.3 Turing's Thesis 244

Chapter 10 Other Models of Turing Machines 249

10.1 Minor Variations on the Turing Machine Theme 250

Equivalence of Classes of Automata 250

Turing Machines with a Stay-Option 251

Turing Machines with Semi-Infinite Tape 253

The Off-Line Turing Machine 255

10.2 Turing Machines with More Complex Storage 258

Multitape Turing Machines 258

Multidimensional Turing Machines 261

10.3 Nondeterministic Turing Machines 263

10.4 A Universal Turing Machine 266

10.5 Linear Bounded Automata 270

Chapter 11 A Hierarchy of Formal Languages and Automata 275

11.1 Recursive and Recursively Enumerable Languages 276

Languages That Are Not Recursively Enumerable 278

A Language That Is Not Recursively Enumerable 279

A Language That Is Recursively Enumerable But Not Recursive 281

11.2 Unrestricted Grammars 283

11.3 Context-Sensitive Grammars and Languages 289

Context-Sensitive Languages and Linear Bounded Automata 290

Relation Between Recursive and Context-Sensitive Languages 292

11.4 The Chomsky Hierarchy 295

Chapter 12 Limits of Algorithmic Computation 299

12.1 Some Problems That Cannot Be Solved By Turing Machines 300

The Turing Machine Halting Problem 301

Reducing One Undecidable Problem to Another 304

12.2 Undecidable Problems for Recursively Enumerable Languages 308

12.3 The Post Correspondence Problem 312

12.4 Undecidable Problems for Context-Free Languages 318

Chapter 13 Other Models of Computation 323

13.1 Recursive Functions 325

Primitive Recursive Functions 326

Ackermann's Function 330

13.2 Post Systems 334

13.3 Rewriting Systems 337

Markov Algorithms 339

L-Systems 340

Chapter 14 An Introduction to Computational Complexity 343

14.1 Efficiency of Computation 344

14.2 Turing Machines and Complexity 346

14.3 Language Families and Complexity Classes 350

14.4 The Complexity Classes P and NP 353

Answers to Selected Exercises 357

References 405

Index 407