形式语言与自动机导论 英文版 第3版PDF|Epub|txt|kindle电子书版本网盘下载

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

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

Chapter 1 Introduction to the Theory of Computation1

1.1 Mathematical Preliminaries and Notation3

Sets3

Functions and Relations5

Graphs and Trees7

Proof Techniques9

1.2 Three Basic Concepts15

Languages15

Grammars19

Automata25

1.3 Some Applications29

Chapter 2 Finite Automata35

2.1 Deterministic Finite Accepters36

Deterministic Accepters and Transition Graphs36

Languages and Dfas38

Regular Languages42

2.2 Nondeterministic Finite Accepters47

Definition of a Nondeterministic Accepter48

Why Nondeterminism?52

2.3 Equivalence of Deterministic and Nondeterministic Finite Accepters55

2.4 Reduction of the Number of States in Finite Automata62

Chapter 3 Regular Languages and Regular Grammars71

3.1 Regular Expressions71

Formal Definition of a Regular Expression72

Languages Associated with Regular Expressions73

3.2 Connection Between Regular Expressions and Regular Languages78

Regular Expressions Denote Regular Languages78

Regular Expressions for Regular Languages81

Regular Expressions for Describing Simple Patterns85

3.3 Regular Grammars89

Right-and Left-Linear Grammars89

Right-Linear Grammars Generate Regular Languages91

Right-Linear Grammars for Regular Languages93

Equivalence Between Regular Languages and Regular Grammars95

Chapter 4 Properties of Regular Languages99

4.1 Closure Properties of Regular Languages100

Closure under Simple Set Operations100

Closure under Other Operations103

4.2 Elementary Questions about Regular Languages111

4.3 Identifying Nonregular Languages114

Using the Pigeonhole Principle114

A Pumping Lemma115

Chapter 5 Context-Free Languages125

5.1 Context-Free Grammars126

Examples of Context-Free Languages127

Leftmost and Rightmost Derivations129

Derivation Trees130

Relation Between Sentential Forms and Derivation Trees132

5.2 Parsing and Ambiguity136

Parsing and Membership136

Ambiguity in Grammars and Languages141

5.3 Context-Free Grammars and Programming Languages146

Chapter 6 Simplification of Context-Free Grammars149

6.1 Methods for Transforming Grammars150

A Useful Substitution Rule150

Removing Useless Productions152

Removing λ-Productions156

Removing Unit-Productions158

6.2 Two Important Normal Forms165

Chomsky Normal Form165

Greibach Normal Form168

6.3 A Membership Algorithm for Context-Free Grammars172

Chapter 7 Pushdown Automata175

7.1 Nondeterministic Pushdown Automata176

Definition of a Pushdown Automaton176

A Language Accepted by a Pushdown Automaton179

7.2 Pushdown Automata and Context-Free Languages184

Pushdown Automata for Context-Free Languages184

Context-Free Grammars for Pushdown Automata189

7.3 Deterministic Pushdown Automata and Deterministic Context-Free Languages195

7.4 Grammars for Deterministic Context-Free Languages200

Chapter 8 Properties of Context-Free Languages205

8.1 Two Pumping Lemmas206

A Pumping Lemma for Context-Free Languages206

A Pumping Lemma for Linear Languages210

8.2 Closure Properties and Decision Algorithms for Context-Free Languages213

Closure of Context-Free Languages213

Some Decidable Properties of Context-Free Languages218

Chapter 9 Turing Machines221

9.1 The Standard Turing Machine222

Definition of a Turing Machine222

Turing Machines as Language Accepters229

Turing Machines as Transducers232

9.2 Combining Turing Machines for Complicated Tasks238

9.3 Turing's Thesis244

Chapter 10 Other Models of Turing Machines249

10.1 Minor Variations on the Turing Machine Theme250

Equivalence of Classes of Automata250

Turing Machines with a Stay-Option251

Turing Machines with Semi-Infinite Tape253

The Off-Line Turing Machine255

10.2 Turing Machines with More Complex Storage258

Multitape Turing Machines258

Multidimensional Turing Machines261

10.3 Nondeterministic Turing Machines263

10.4 A Universal Turing Machine266

10.5 Linear Bounded Automata270

Chapter 11 A Hierarchy of Formal Languages and Automata275

11.1 Recursive and Recursively Enumerable Languages276

Languages That Are Not Recursively Enumerable278

A Language That Is Not Recursively Enumerable279

A Language That Is Recursively Enumerable But Not Recursive281

11.2 Unrestricted Grammars283

11.3 Context-Sensitive Grammars and Languages289

Context-Sensitive Languages and Linear Bounded Automata290

Relation Between Recursive and Context-Sensitive Languages292

11.4 The Chomsky Hierarchy295

Chapter 12 Limits of Algorithmic Computation299

12.1 Some Problems That Cannot Be Solved By Turing Machines300

The Turing Machine Halting Problem301

Reducing One Undecidable Problem to Another304

12.2 Undecidable Problems for Recursively Enumerable Languages308

12.3 The Post Correspondence Problem312

12.4 Undecidable Problems for Context-Free Languages318

Chapter 13 Other Models of Computation323

13.1 Recursive Functions325

Primitive Recursive Functions326

Ackermann's Function330

13.2 Post Systems334

13.3 Rewriting Systems337

Markov Algorithms339

L-Systems340

Chapter 14 An Introduction to Computational Complexity343

14.1 Efficiency of Computation344

14.2 Turing Machines and Complexity346

14.3 Language Families and Complexity Classes350

14.4 The Complexity Classes P and NP353

Answers to Selected Exercises357

References405

Index407