图书介绍
自动机理论与应用pdf电子书版本下载
- （美）里奇著 著
- 出版社： 北京：清华大学出版社
- ISBN：9787302265863
- 出版时间：2011
- 标注页数：525页
- 文件大小：166MB
- 文件页数：544页
- 主题词：自动机理论－教材
PDF下载
下载说明
自动机理论与应用PDF格式电子书版下载
下载的文件为RAR压缩包。需要使用解压软件进行解压得到PDF格式图书。建议使用BT下载工具Free Download Manager进行下载,简称FDM(免费,没有广告,支持多平台）。本站资源全部打包为BT种子。所以需要使用专业的BT下载软件进行下载。如 BitComet qBittorrent uTorrent等BT下载工具。迅雷目前由于本站不是热门资源。不推荐使用！后期资源热门了。安装了迅雷也可以迅雷进行下载！
（文件页数 要大于 标注页数，上中下等多册电子书除外）
注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具
图书目录
第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 非确定性FSM 46
5.4.1 什么是非确定性FSM 47
5.4.2 模式与子串匹配的NDFSM 49
5.4.3 分析非确定FSM 50
5.4.4 确定FSM与非确定FSM的等价性 52
5.5 从FSM到操作系统 56
5.6 FSM模拟 56
5.6.1 模拟确定FSM 56
5.6.2 模拟非确定FSM 57
5.7 简化FSM 58
5.7.1 建立一种语言的最简DFSM 58
5.7.2 简化DFSM 63
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 建立正则表达式的FSM 92
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 确定性与非确定性PDA 180
12.2.1 确定性PDA的定义 180
12.2.2 了解非确定性 181
12.2.3 减少非确定性 183
12.3 上下文无关文法与PDA的等价性 184
12.3.1 建立一个文法的PDA 184
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或？SD 341
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 复杂度0 416
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 语言类P 439
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 语言类NP 447
28.2.1 定义NP类 447
28.2.2 NP语言 449
28.2.3 TSP 451
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-SAT 464
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 EXPTIME 483
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与ZPP 510
30.2.3 测试质数性 513
30.3 启发式搜索 515
30.3.1 启发式搜索简介 515
30.3.2 A*算法 517
练习 521
第31章 小结与参考资料 523
参考资料 523