形式语言与自动机导论

封面
书名
版权
前言
目录
目录
出版者的话
专家指导委员会
译者序
前言
第1章　计算理论导引
1 1　数学预备知识和表示
1 1 1　集合
1 1 2　函数和关系
1 1 3　图和树
1 1 4　证明方法
1 2  三个基本概念
1 2 1　语言
1 2 2　文法
1 2 3　自动机
1 3  一些应用＊
2 1 1　确定型接受器和转换图
第2章  有穷自动机
2 1　确定型有穷接受器
2 1 2　语言和dfa对应的语言
2 1 3　正则语言
2 2　非确定型有穷接受器
2 2 1　非确定型接受器的定义
2 2 2　为什么需要非确定型
2 3　确定型有穷接受器和非确定型有穷接受器的等价性
2 4　减少有穷自动机中状态的化简＊
第3章　正则语言与正则文法
3 1　正则表达式
3 1 1　正则表达式的形式化定义
3 1 2　和正则表达式相关的语言
3 2　正则表达式和正则语言之间的联系
3 2 1　正则表达式表示正则语言
3 2 2　正则语言的正则表达式
3 2 3　描述简单模式的正则表达式
3 3　正则文法
3 3 1　右线性文法和左线性文法
3 3 2　右线性文法生成正则语言
3 3 3　正则语言的右线性文法
3 3 4　正则语言和正则文法的等价性
第4章　正则语言的性质
4 1　正则语言的封闭性质
4 1 1　简单集合运算的封闭性
4 1 2　其他运算的封闭性
4 2　正则语言的基本问题
4 3　识别非正则语言
4 3 1　使用鸽巢原理
4 3 2　泵引理
第5章　上下文无关语言
5 1　上下文无关文法
5 1 1  上下文无关语言的例子
5 1 2  最左推导和最右推导
5 1 3　推导树
5 1 4　句型和推导树之间的关系
5 2　分析和二义性
5 2 1　分析和成员资格判定
5 2 2　文法和语言的二义性
5 3　上下文无关文法和程序设计语言
6 1　文法变换方法
6 1 1　一个有用的代入规则
第6章　上下文无关文法的化简与范式
6 1 2　删除无用产生式
6 1 3　消除λ产生式
6 1 4　消除单位产生式
6 2　两个重要的范式
6 2 1　乔姆斯基范式
6 2 2　格里巴克范式
6 3　上下文无关文法的成员资格
判定算法＊
7 1　非确定型下推自动机
第7章  下推自动机
7 1 1　下推自动机的定义
7 1 2　下推自动机接受的语言
7 2　下推自动机与上下文无关语言
7 2 1　上下文无关语言相应的下推自动机
7 2 2　下推自动机相应的上下文无关文法
7 3　确定型下推自动机和确定型上下文无关语言
7 4　确定型上下文无关语言的文法＊
第8章　上下文无关语言的性质
8 1　两个泵引理
8 1 1　上下文无关语言的泵引理
8 1 2　线性语言的泵引理
8 2　上下文无关语言的封闭性质和判定算法
8 2 1　上下文无关语言的封闭性质
8 2 2　上下文无关语言的可判定性质
9 1　标准图灵机
9 1 1　图灵机的定义
第9章　图灵机
9 1 2　作为语言接受器的图灵机
9 1 3　作为转换器的图灵机
9 2　完成复杂任务的组合图灵机
9 3　图灵论题
第10章　图灵机的其他模型
10 1　对图灵机的较小修改
10 1 1　自动机类的等价性
10 1 2  带不动选择的图灵机
10 1 3　单向无穷带图灵机
10 1 4　离线图灵机
10 2　具有更复杂存储的图灵机
10 2 1　多带图灵机
10 2 2　多维图灵机
10 3　非确定型图灵机
10 4　通用图灵机
10 5　线性有界自动机
11 1　递归语言和递归可枚举语言
第11章　形式语言和自动机的层次结构
11 1 1　非递归可枚举的语言
11 1 2　非递归可枚举语言
11 1 3　递归可枚举但非递归的语言
11 2　无限制文法
11 3　上下文相关文法和语言
11 3 1　上下文相关语言和线性有界自动机
11 3 2　递归语言和上下文相关语言的关系
11 4  乔姆斯基层次结构
第12章　算法计算的限制
12 1　图灵机所不能解决的问题
12 1 1　可计算性和可判定性
12 1 2　图灵机停机问题
12 1 3　将一个不可判定问题简化成另外一个问题
12 2　递归可枚举语言的不可判定问题
12 3　波斯特对应问题
12 4　上下文无关语言的不可判定问题
第13章  其他的计算模型
13 1　递归函数
13 1 1　原始递归函数
13 1 2　Ackermann函数
13 1 3　μ递归函数
13 2　波斯特系统
13 3　重写系统
13 3 1　矩阵文法
13 3 2　马尔科夫算法
13 3 3  L系统
第14章  计算复杂性介绍
14 1　计算的效率
14 2　图灵机和复杂性
14 3　语言族和复杂性类
14 4　复杂性类P和NP
部分习题的解答和提示
参考文献
索引