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

点此进入-本书在线PDF格式电子书下载【推荐-云解压-方便快捷】直接下载PDF格式图书。移动端-PC端通用
种子下载[BT下载速度快] 温馨提示：（请使用BT下载软件FDM进行下载）软件下载地址页 直链下载[便捷但速度慢]   [在线试读本书]   [在线获取解压码]

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

下载的文件为RAR压缩包。需要使用解压软件进行解压得到PDF格式图书。

建议使用BT下载工具Free Download Manager进行下载,简称FDM(免费,没有广告,支持多平台）。本站资源全部打包为BT种子。所以需要使用专业的BT下载软件进行下载。如 BitComet qBittorrent uTorrent等BT下载工具。迅雷目前由于本站不是热门资源。不推荐使用！后期资源热门了。安装了迅雷也可以迅雷进行下载！

（文件页数 要大于 标注页数，上中下等多册电子书除外）

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

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