自动机理论与应用PDF|Epub|txt|kindle电子书版本网盘下载

自动机理论与应用PDF格式电子书版下载

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

第1部分 简介3

第1章 为什么学习计算理论3

1.1 编程工具的历史3

1.2 理论的应用无处不在5

第2章 语言与字符串7

2.1 字符串7

2.1.1 字符串函数7

2.1.2 字符串的关系8

2.2 语言9

2.2.1 定义语言的方法9

2.2.2 语言的势11

2.2.3 有多少语言11

2.2.4 语言函数12

2.2.5 对语言字符串赋予意义14

练习15

第3章 语言层次16

3.1 定义任务：语言识别16

3.2 编码的力量16

3.2.1 一切都是字符串16

3.2.2 把问题变成决策问题19

3.3 基于机器的语言类层次20

3.3.1 正则语言20

3.3.2 上下文无关语言21

3.3.3 可确定和半确定语言22

3.3.4 计算层次及其重要性23

3.4 语言类的可跟踪性层次24

练习25

第4章 计算26

4.1 决策过程26

4.2 确定性与非确定性29

4.3 语言与程序的函数33

练习35

第2部分 有限状态机与正则语言第5章 有限状态机39

5.1 确定性有限状态机40

5.2 正则语言43

5.3 设计确定性有限状态机44

5.4 非确定性FSM46

5.4.1 什么是非确定性FSM47

5.4.2 模式与子串匹配的NDFSM49

5.4.3 分析非确定FSM50

5.4.4 确定FSM与非确定FSM的等价性52

5.5 从FSM到操作系统56

5.6 FSM模拟56

5.6.1 模拟确定FSM56

5.6.2 模拟非确定FSM57

5.7 简化FSM58

5.7.1 建立一种语言的最简DFSM58

5.7.2 简化DFSM63

5.8 正则语言的规范形式66

5.9 有限状态变换器67

5.10 双向变换器69

5.11 随机有限自动机：Markov模型与隐藏Markov模型70

5.11.1 Markov模型71

5.11.2 隐马模型74

5.12 有限自动机、无限字符串：Büchi自动机79

练习83

第6章 正则表达式88

6.1 什么是正则表达式88

6.2 Kleene定理91

6.2.1 建立正则表达式的FSM92

6.2.2 从FSM建立正则表达式94

6.2.3 正则表达式与FSM的等价性99

6.2.4 Kleene定理、正则表达式和有限状态机99

6.3 应用正则表达式102

6.4 操纵和简化正则表达式103

练习105

第7章 正则文法108

7.1 正则文法的定义108

7.2 正则文法与正则语言109

练习112

第8章 正则与非正则语言113

8.1 有多少正则语言113

8.2 证明一个语言是正则语言113

8.3 正则语言的一些闭包属性115

8.4 证明一个语言不是正则117

8.4.1 正则语言的泵定理118

8.4.2 使用闭包属性122

8.5 利用问题特定知识123

8.6 正则语言的函数124

练习126

第9章 正则语言的算法与决策过程130

9.1 基本决策过程130

9.1.1 成员关系130

9.1.2 空性与整体性131

9.1.3 有限性133

9.1.4 等价性134

9.1.5 最简性134

9.1.6 综合回答特定问题135

9.2 正则语言算法与决策过程小结135

练习136

第10章 小结与参考资料138

参考资料139

第3部分 上下文无关语言与压栈自动机第11章 上下文无关文法143

11.1 改写系统与文法简介143

11.2 上下文无关文法与语言145

11.3 设计上下文无关文法149

11.4 简化上下文无关文法150

11.5 证明文法正确151

11.6 推导与解析树154

11.7 歧义性155

11.7.1 歧义性有什么问题156

11.7.2 固有歧义性157

11.7.3 消歧文法158

11.8 范式164

11.8.1 文法的范式164

11.8.2 变成范式165

11.8.3 变成Chomsky范式166

11.8.4 范式的代价170

11.9 孤岛文法170

11.10 随机上下文无关文法172

练习173

第12章 压栈自动机177

12.1 非确定性压栈自动机的定义177

12.2 确定性与非确定性PDA180

12.2.1 确定性PDA的定义180

12.2.2 了解非确定性181

12.2.3 减少非确定性183

12.3 上下文无关文法与PDA的等价性184

12.3.1 建立一个文法的PDA184

12.3.2 建立一个PDA的文法188

12.3.3 上下文无关文法与PDA的等价性193

12.4 非确定性与停机193

12.5 PDA的其他等价定义195

12.6 不等价于PDA的情形196

练习196

第13章 上下文无关与非上下文无关语言197

13.1 上下文无关语言的地位197

13.2 证明一种语言为上下文无关语言198

13.3 上下文无关语言的泵定理198

13.4 上下文无关语言一些重要闭包属性203

13.4.1 闭包定理203

13.4.2 泵定理和闭合属性一起使用205

13.5 确定性上下文无关语言207

13.6 Ogden推论213

13.7 Parikh定理215

13.8 上下文无关语言函数217

练习218

第14章 上下文无关语言的算法与决策过程222

14.1 可确定问题222

14.1.1 成员关系222

14.1.2 空性与有限性225

14.1.3 确定性上下文无关语言的相等性226

14.2 不可确定问题226

14.3 上下文无关语言算法与决策过程小结226

练习227

第15章 上下文无关解析228

15.1 辞典分析229

15.2 自顶向下解析230

15.2.1 深度优先搜索231

15.2.2 修改自顶向下解析的文法233

15.2.3 确定性自顶向下解析与LL（1）文法237

15.3 自下而上解析240

15.3.1 Cocke-Kasami-Younger算法240

15.3.2 上下文无关解析与矩阵乘法243

15.3.3 移位减少解析243

15.3.4 确定性自下而上LR解析247

15.4 解析自然语言248

15.4.1 问题248

15.4.2 Earley算法248

练习254

第16章 小结与参考资料255

参考资料255

第4部分 图灵机与不可确定性第17章 图灵机259

17.1 定义、符号与例子259

17.1.1 什么是图灵机259

1 7.1.2 图灵机编程262

17.1.3 停机263

17.1.4 形式化图灵机操作263

17.1.5 图灵机的宏记法264

17.2 用图灵机计算267

17.2.1 用图灵机作为语言识别器267

17.2.2 图灵机计算函数270

17.3 增加多个磁带和非确定性272

17.3.1 多带272

17.3.2 非确定性图灵机276

17.4 模拟实际计算机279

17.5 其他图灵机定义282

17.5.1 单向与双向无限带282

17.5.2 堆栈与磁带283

17.6 将图灵机编码成字符串284

17.6.1 图灵机编码模式285

17.6.2 枚举图灵机286

17.6.3 编码的另一个好处287

17.6.4 编码一个图灵机的多个输入287

17.7 万能图灵机288

练习289

第18章 Church-Turing命题293

18.1 命题293

18.2 等价形式例子295

18.2.1 现代计算机295

18.2.2 Lambda演算295

18.2.3 标注系统296

18.2.4 Post生产系统296

18.2.5 无限制文法297

18.2.6 Markov算法298

18.2.7 Conway生命游戏299

18.2.8 一维基本元胞自动机299

18.2.9 DNA计算300

练习301

第19章 停止问题的不可解决性303

19.1 语言H是半确定的但不是确定的304

19.2 H不可确定性的一些意义306

19.3 回到图灵、Church和决策问题307

练习308

第20章 可确定与半确定语言309

20.1 D概述309

20.2 SD概述309

20.3 D与SD之间的子集关系310

20.4 D与SD类的补集311

20.5 枚举语言312

20.5.1 按未定义顺序枚举312

20.5.2 辞典顺序枚举314

20.6 小结315

练习316

第21章 可确定性与不可确定性证明318

21.1 归约法318

21.2 用归约法证明一个语言不是可确定的320

21.2.1 映射归约性322

21.2.2 不是映射归约的归约329

21.3 是不是图灵机的所有问题都不可确定330

21.4 Rice定理331

21.5 实际程序的不可确定问题334

21.6 证明一个语言不是半确定336

21.6.1 非归约法336

21.6.2 归约法337

21.6.3 L是否在D、SD/D或？SD341

21.7 包括图灵机描述的D、SD/D和？SD语言小结341

练习342

第22章 不明显提图灵机问题的语言的可确定性345

22.1 Diophantine方程与Hilbert第十问题345

22.2 Post对应性问题346

22.3 铺砖问题348

22.4 逻辑理论350

22.4.1 布尔理论351

22.4.2 一阶逻辑理论351

22.5 上下文无关语言的不可确定问题353

22.5.1 通过计算历史归约354

22.5.2 使用CFGALL的不可确定性356

22.5.3 从PCP归约357

练习359

第23章 无限制文法361

23.1 定义和例子361

23.2 非限制文法与图灵机的等价性365

23.3 文法计算函数366

23.4 无限制文法的不可确定问题368

23.5 半Thue系统的单词问题369

练习370

第24章 Chomsky层次及其他371

24.1 上下文有关语言371

24.1.1 线性有界自动机确定372

24.1.2 上下文有关文法373

24.1.3 线性有界自动机与上下文有关文法的等价性374

24.1.4 上下文有关语言在语言层次中的位置374

24.1.5 上下文有关语言的闭包属性376

24.1.6 上下文有关语言的决策过程378

24.2 Chomsky层次380

24.3 属性、特性与合一文法381

24.4 Lindenmayer系统383

练习389

第25章 可计算函数391

25.1 什么是可计算函数391

25.1.1 总体与部分函数391

25.1.2 部分可计算与可计算函数392

25.1.3 不是部分可计算的函数394

25.1.4 忙海狸函数395

25.1.5 语言与函数397

25.2 递归函数理论398

25.2.1 基本递归函数398

25.2.2 Ackermann函数400

25.2.3 可递归（可计算）函数401

25.3 递归定理及其使用403

练习408

第26章 小结与参考资料410

参考资料411

第5部分 复杂度415

第27章 复杂度分析简介415

27.1 旅行销售员问题415

27.2 复杂度0416

27.3 问题特性化417

27.3.1 选择编码方式417

27.3.2 把优化问题变成语言419

27.4 测量时间与空间复杂度419

27.4.1 选择计算模型419

27.4.2 定义测量时间与空间要求的函数420

27.5 函数增长速率422

27.6 渐近优势423

27.7 算法空白427

27.8 例子427

27.8.1 多项式加速427

27.8.2 将指数级算法变成多项式算法433

27.8.3 时间空间取舍434

练习435

第28章 时间复杂度类439

28.1 语言类P439

28.1.1 P在补集下闭合439

28.1.2 属于P的语言440

28.1.3 正则下上下文无关语言441

28.1.4 连通图441

28.1.5 欧拉路径与线路442

28.1.6 最小生成树444

28.1.7 质数性测试446

28.2 语言类NP447

28.2.1 定义NP类447

28.2.2 NP语言449

28.2.3 TSP451

28.2.4 集团探测451

28.2.5 布尔可满足性452

28.3 P=NP？453

28.4 用归约法进行复杂度证明454

28.5 NP完备性与Cook-Levin定理456

28.5.1 NP完备与NP难语言457

28.5.2 Cook-Levin定理和SAT的NP完备性458

28.6 其他NP完备问题462

28.6.1 NP完备问题采样462

28.6.2 证明一个语言为NP完备463

28.6.3 3-SAT464

28.6.4 独立集合465

28.6.5 VERTEX-COVER（顶点覆盖）465

28.6.6 哈密尔顿线路与旅行销售员问题467

28.7 P与NP完备的关系473

28.7.1 P与NP完备间的空白473

28.7.2 两个类似的线路问题474

28.7.3 两个类似的SAT问题474

28.7.4 两个类似的路径问题474

28.7.5 两个相似的覆盖问题475

28.7.6 三个类似的地图作色问题476

28.7.7 两个类似的线性编程问题477

28.7.8 Diophantine方程问题的层次478

28.8 Co-NP语言类478

28.9 时间层次定理、EXPTIME及其他479

28.9.1 时间层次定理480

28.9.2 EXPTIME483

28.9.3 比EXPTIME更难的问题484

28.10 FP与FNP问题类484

练习485

第29章 空间复杂度类490

29.1 分析空间复杂度类490

29.1.1 例子490

29.1.2 时间与空间复杂度关系492

29.2 PSPACE、NPSPACE与Savitch定理493

29.3 PSPACE完备性496

29.3.1 QBF语言497

29.3.2 QBF是PSPACE完备的498

29.3.3 其他PSPACE难题与PSPACE完备问题501

29.4 次线性空间复杂度502

29.5 空间复杂度类在补集下闭合505

29.6 空间层次定理506

第30章 难题的实用解508

30.1 方法508

30.2 随机算法和BPP、RP、Co-RP与ZPP语言类509

30.2.1 随机算法509

30.2.2 语言类BPP、RP、Co-RP与ZPP510

30.2.3 测试质数性513

30.3 启发式搜索515

30.3.1 启发式搜索简介515

30.3.2 A*算法517

练习521

第31章 小结与参考资料523

参考资料523