形式语言与自动机导论 原书第3版PDF电子书下载

目录 1

出版者的话 1

专家指导委员会 1

译者序 1

前言 1

第1章　计算理论导引 1

1 1　数学预备知识和表示 2

1 1 1　集合 2

1 1 2　函数和关系 3

1 1 3　图和树 5

1 1 4　证明方法 7

1 2 三个基本概念 10

1 2 1　语言 11

1 2 2　文法 13

1 2 3　自动机 18

1 3 一些应用＊ 21

2 1 1　确定型接受器和转换图 27

第2章 有穷自动机 27

2 1　确定型有穷接受器 27

2 1 2　语言和dfa对应的语言 29

2 1 3　正则语言 32

2 2　非确定型有穷接受器 35

2 2 1　非确定型接受器的定义 35

2 2 2　为什么需要非确定型 38

2 3　确定型有穷接受器和非确定型有穷接受器的等价性 40

2 4　减少有穷自动机中状态的化简＊ 45

第3章　正则语言与正则文法 51

3 1　正则表达式 51

3 1 1　正则表达式的形式化定义 51

3 1 2　和正则表达式相关的语言 51

3 2　正则表达式和正则语言之间的联系 55

3 2 1　正则表达式表示正则语言 55

3 2 2　正则语言的正则表达式 56

3 2 3　描述简单模式的正则表达式 59

3 3　正则文法 62

3 3 1　右线性文法和左线性文法 62

3 3 2　右线性文法生成正则语言 63

3 3 3　正则语言的右线性文法 64

3 3 4　正则语言和正则文法的等价性 66

第4章　正则语言的性质 69

4 1　正则语言的封闭性质 69

4 1 1　简单集合运算的封闭性 70

4 1 2　其他运算的封闭性 71

4 2　正则语言的基本问题 77

4 3　识别非正则语言 78

4 3 1　使用鸽巢原理 79

4 3 2　泵引理 79

第5章　上下文无关语言 85

5 1　上下文无关文法 85

5 1 1 上下文无关语言的例子 86

5 1 2 最左推导和最右推导 87

5 1 3　推导树 88

5 1 4　句型和推导树之间的关系 89

5 2　分析和二义性 92

5 2 1　分析和成员资格判定 92

5 2 2　文法和语言的二义性 95

5 3　上下文无关文法和程序设计语言 99

6 1　文法变换方法 101

6 1 1　一个有用的代入规则 101

第6章　上下文无关文法的化简与范式 101

6 1 2　删除无用产生式 103

6 1 3　消除λ产生式 106

6 1 4　消除单位产生式 107

6 2　两个重要的范式 111

6 2 1　乔姆斯基范式 112

6 2 2　格里巴克范式 114

6 3　上下文无关文法的成员资格 116

判定算法＊ 116

7 1　非确定型下推自动机 119

第7章 下推自动机 119

7 1 1　下推自动机的定义 120

7 1 2　下推自动机接受的语言 121

7 2　下推自动机与上下文无关语言 125

7 2 1　上下文无关语言相应的下推自动机 125

7 2 2　下推自动机相应的上下文无关文法 129

7 3　确定型下推自动机和确定型上下文无关语言 133

7 4　确定型上下文无关语言的文法＊ 136

第8章　上下文无关语言的性质 141

8 1　两个泵引理 141

8 1 1　上下文无关语言的泵引理 141

8 1 2　线性语言的泵引理 144

8 2　上下文无关语言的封闭性质和判定算法 146

8 2 1　上下文无关语言的封闭性质 146

8 2 2　上下文无关语言的可判定性质 149

9 1　标准图灵机 153

9 1 1　图灵机的定义 153

第9章　图灵机 153

9 1 2　作为语言接受器的图灵机 157

9 1 3　作为转换器的图灵机 160

9 2　完成复杂任务的组合图灵机 164

9 3　图灵论题 168

第10章　图灵机的其他模型 171

10 1　对图灵机的较小修改 171

10 1 1　自动机类的等价性 171

10 1 2 带不动选择的图灵机 172

10 1 3　单向无穷带图灵机 174

10 1 4　离线图灵机 175

10 2　具有更复杂存储的图灵机 177

10 2 1　多带图灵机 177

10 2 2　多维图灵机 179

10 3　非确定型图灵机 181

10 4　通用图灵机 183

10 5　线性有界自动机 186

11 1　递归语言和递归可枚举语言 189

第11章　形式语言和自动机的层次结构 189

11 1 1　非递归可枚举的语言 190

11 1 2　非递归可枚举语言 191

11 1 3　递归可枚举但非递归的语言 192

11 2　无限制文法 193

11 3　上下文相关文法和语言 198

11 3 1　上下文相关语言和线性有界自动机 198

11 3 2　递归语言和上下文相关语言的关系 199

11 4 乔姆斯基层次结构 201

第12章　算法计算的限制 205

12 1　图灵机所不能解决的问题 205

12 1 1　可计算性和可判定性 205

12 1 2　图灵机停机问题 206

12 1 3　将一个不可判定问题简化成另外一个问题 208

12 2　递归可枚举语言的不可判定问题 211

12 3　波斯特对应问题 213

12 4　上下文无关语言的不可判定问题 218

第13章 其他的计算模型 223

13 1　递归函数 224

13 1 1　原始递归函数 225

13 1 2　Ackermann函数 227

13 1 3　μ递归函数 228

13 2　波斯特系统 229

13 3　重写系统 232

13 3 1　矩阵文法 232

13 3 2　马尔科夫算法 233

13 3 3 L系统 234

第14章 计算复杂性介绍 237

14 1　计算的效率 237

14 2　图灵机和复杂性 239

14 3　语言族和复杂性类 241

14 4　复杂性类P和NP 243

部分习题的解答和提示 247

参考文献 283

索引 285