文件名称：自动机理论、语言和计算导引
文件大小：8.95MB
文件格式：PDF
更新时间：2011-08-07 03:41:15
自动机理论 语言 计算 文化基础
虽然不是入门教材，但个人感觉这才是真正的“计算机文化基础”，看看章节目录就会爱不释手。
目录
1、1字符串、字母表和语言
第一章 预备知识
1、2图和树
1、3归纳证明
1、4集合
1、5关系
1、6本书提要
2、1有穷状态系统
第二章 有穷自动机和正规表达式
2、2基本定义
2、3非确定有穷自动机
2、4具有∈动作的有穷自动机
2、5正规表达式
2、6双向有穷自动机
2、7具有输出的有穷自动机
2、8有穷自动机的应用
3、1正规集合的泵作用引理
第三章 正规集合的性质
3、2正规集合的封闭性质
3、3正规集合的判定算法
3、4Myhill-Nerode定理和有穷自动机的最小化
4、1动机和引言
第四章 上下文无关文法
4、2上下文无关文法
4、3派生树
4、4上下文无关文法的简化
4、5Chomsky范式
4、6Greibach范式
4、7固有多义上下文无关语言的存在性
5、1非形式描述
第五章 下推自动机
5、2定义
5、3下推自动机和上下文无关语言
6、1关于CFL的泵作用引理
第六章 上下文无关语言的性质
6、2CFL的封闭性质
6、3有关CFL的判定算法
7、1引言
第七章 图灵机
7、2图灵机模型
7、3可计算语言和可计算函数
7、4图灵机构造技术
7、5图灵机的修改
7、6Church假设
7、7作为枚举器的图灵机
7、8等价于基本模型的受限图灵机
8、1问题
第八章 不可判定性
8、2递归语言和递归可枚举语言的性质
8、3通用图灵机和一个不可判定问题
8、4Rice定理和某些其它的不可判定问题
8、5Post对应问题的不可判定性
8、6图灵机的有效计算和无效计算：证明CFL问题不可判定性的一个工具
8、7Greibach定理
8、8递归函数论初步
8、9Oracle计算
9、1正规文法
第九章 Chomsky谱系
9、2无限制文法
9、3上下文有关语言
9、4语言类之间的关系
第十章 确定的上下文无关语言
10、1DPDA的标准形式
10、2DCFL在补运算下的封闭性
10、3预测机
10、4DCFL的其它封闭性质
10、5DCFL的判定性质
10、6LR（0）文法
10、7LR（0）文法与DPDA
10、8LR（k）文法
11、1三元族和完全三元族
第十一章 语言族的封闭性质
11、2广义时序机映射
11、3三元族的其它封闭性质
11、4抽象语言族
11、5AFL运算的独立性
11、6小结
12、1定义
第十二章 计算复杂性理论
12、2线性加速、带压缩和带数目的减少
12、3谱系定理
12、4复杂性量度间的关系
12、5转换引理和非确定谱系
12、6一般复杂性量度的性质：间隙定理、加速定理和并定理
12、7公理化复杂性理论
13、1多项式时间和空间
第十三章 难解型问题
13、2某些NP完全问题
13、3co-NP类
13、4PSPACE完全问题
13、5对于P和NSPACE（logn）的完全问题
13、6某些可证明的难解型问题
13、7对于带Oracle的图灵机的P=NP问题：辨别是否P=NP时我们能力的限度
14、1辅助下推自动机
第十四章 其它重要语言类集锦
14、2栈自动机
14、3加标语言
14、4发展系统
14、5小结
参考文献
汉英名词索引