图书介绍
自动机理论、语言和计算导引PDF|Epub|txt|kindle电子书版本网盘下载
- （美）J.E. 霍普克罗夫特，（美）J.D. 厄尔曼著；徐美瑞译 著
- 出版社： 北京：科学出版社
- ISBN：15031·737
- 出版时间：1986
- 标注页数：528页
- 文件大小：9MB
- 文件页数：539页
- 主题词：
PDF下载
下载说明
自动机理论、语言和计算导引PDF格式电子书版下载
下载的文件为RAR压缩包。需要使用解压软件进行解压得到PDF格式图书。建议使用BT下载工具Free Download Manager进行下载,简称FDM(免费,没有广告,支持多平台）。本站资源全部打包为BT种子。所以需要使用专业的BT下载软件进行下载。如BitComet qBittorrent uTorrent等BT下载工具。迅雷目前由于本站不是热门资源。不推荐使用！后期资源热门了。安装了迅雷也可以迅雷进行下载！
（文件页数 要大于 标注页数，上中下等多册电子书除外）
注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具
图书目录
第一章 预备知识1
1.1 字符串、字母表和语言1
1.2 图和树2
1.3 归纳证明4
1.4 集合5
1.5 关系8
1.6 本书提要10
第二章 有穷自动机和正规表达式15
2.1 有穷状态系统15
2.2 基本定义18
2.3 非确定有穷自动机22
2.4 具有？动作的有穷自动机28
2.5 正规表达式33
2.6 双向有穷自动机43
2.7 具有输出的有穷自动机51
2.8 有穷自动机的应用55
第三章 正规集合的性质67
3.1 正规集合的泵作用引理67
3.2 正规集合的封闭性质71
3.3 正规集合的判定算法77
3.4 Myhill-Nerode定理和有穷自动机的最小化79
第四章 上下文无关文法94
4.1 动机和引言94
4.2 上下文无关文法96
4.3 派生树100
4.4 上下文无关文法的简化107
4.5 Chomsky范式115
4.6 Greibach范式118
4.7 固有多义上下文无关语言的存在性123
第五章 下推自动机134
5.1 非形式描述134
5.2 定义136
5.3 下推自动机和上下文无关语言142
第六章 上下文无关语言的性质156
6.1 关于CFL的泵作用引理156
6.2 CFL的封闭性质162
6.3 有关CFL的判定算法171
7.1 引言184
第七章 图灵机184
7.2 图灵机模型185
7.3 可计算语言和可计算函数189
7.4 图灵机构造技术192
7.5 图灵机的修改200
7.6 Church假设208
7.7 作为枚举器的图灵机210
7.8 等价于基本模型的受限图灵机214
第八章 不可判定性222
8.1 问题222
8.2 递归语言和递归可枚举语言的性质224
8.3 通用图灵机和一个不可判定问题227
8.4 Rice定理和某些其它的不可判定问题232
8.5 Post对应问题的不可判定性243
8.6 图灵机的有效计算和无效计算，证明CFL问题不可判定性的一个工具253
8.7 Greibach定理258
8.8 递归函数论初步261
8.9 Oracle计算264
第九章 Chomsky谱系274
9.1 正规文法274
9.2 无限制文法278
9.3 上下文有关语言282
9.4 语言类之间的关系287
第十章 确定的上下文无关语言294
10.1 DPDA的标准形式295
10.2 DCFL在补运算下的封闭性297
10.3 预测机303
10.4 DCFL的其它封闭性质308
10.5 DCFL的判定性质312
10.6 LR(O)文法314
10.7 LR(O)文法与DRDA322
10.8 LR(K)文法332
第十一章 语言族的封闭性质343
11.1 三元族和完全三元族343
11.2 广义时序机映射345
11.3 三元族的其它封闭性质351
11.4 抽象语言族352
11.5 AFL运算的独立性354
11.6 小结355
第十二章 计算复杂性理论362
12.1 定义362
12.2 线性加速、带压缩和带数目的减少365
12.3 谱系定理374
12.4 复杂性量度间的关系381
12.5 转换引理和非确定谱系385
12.6 一般复杂性量度的性质，间隙定理、加速定理和并定理389
12.7 公理化复杂性理论399
第十三章 难解型问题409
13.1 多项式时间和空间409
13.2 某些NP完全问题414
13.3 CO-？？类437
13.4 PSPACE完全问题439
13.5 对于？和NSPACE(logn)的完全问题444
13.6 某些可证明的难解型问题448
13.7 对于带Oracle的图灵机的？=？？问题：辨别是否？=？？时我们能力的限度463
第十四章 其它重要语言类集锦481
14.1 辅助下推自动机481
14.2 栈自动机486
14.3 加标语言496
14.4 发展系统498
14.5 小结500
参考文献504
汉英名词索引519