形式语言与自动机导论（原书第3版）

　　出版者的话
　　专家指导委员会
　　译者序
　　前言
　　第1章  计算理论导引  1
　　1.1数学预备知识和表示  2
　　1.1.1集合  2
　　1.1.2函数和关系  3
　　1.1.3图和树  5
　　1.1.4证明方法  7
　　1.2三个基本概念  l0
　　1.2.1语言  11
　　1.2.2文法  13
　　1.2.3自动机  l8
　　1.3一些应用  2l
　　第2章  有穷自动机  27
　　2.1确定型有穷接受器  27
　　2.1.1确定型接受器和转换图  27
　　2.1.2语言和dfa对应的语言  29
　　2.1.3正则语言  32
　　2.2非确定型有穷接受器  35
　　2.2.1非确定型接受器的定义  35
　　2.2.2为什么需要非确定型  38
　　2.3确定型有穷接受器和非确定型有穷接受器的等价性  4O
　　2.4减少有穷自动机中状态的化简  45
　　第3章  正则语言与正则文法  5l
　　3.1正则表达式  5l
　　3.1.1正则表达式的形式化定义  5l
　　3.1.2和正则表达式相关的语言  5l
　　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简单集合运算的封闭性  7O
　　4.1.2其他运算的封闭性  7l
　　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章  上下文无关文法的化简与范式  101
　　6.1文法变换方法  101
　　6.1.1一个有用的代入规则  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
　　第7章  下推自动机  119
　　7.1非确定型下推自动机  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章  图灵机  153
　　9.1标准图灵机  153
　　9.1.1图灵机的定义  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章  形式语言和自动机的层次结构  189
　　11.1递归语言和递归可枚举语言  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波斯特对应问题  2l3
　　12.4上下文无关语言的不可判定问题  2l8
　　第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

　　Peter Linz，加利福尼亚大学戴维斯分校计算机科学系的荣誉教授，研究重点是：开发数值分析理论，以构建可靠的数值方法并将其用于科学计算中的问题求解环境的设计。Linz教授的相关著作还有Exploring Numerical  Methods：An Introduction in Scientific Computing。

　　主要介绍形式语言、自动机、可计算性和相关内容。本书特别注意定义、定理的准确性和严格性，在定理的证明中给出了直观的动机和框架，避免多余的数学细节，这有利于培养学生形式化和严格的数学推理能力，加强对问题的理解；本书通过精心设计的大量示例，生动剖析了各种定理和定义，概念清晰，深入浅出。每章后面还给出了难度不同的习题，并给出部分习题的解答，可使学生加深对基本原理的理解并增强应用能力。
　　本书主要介绍形式语言、自动机、可计算性和相关内容。主要内容包括：计算理论导引、有穷自动机、正则语言与正则文法、上下文无关语言及文法、下推自动机、图灵机、形式语言和自动机的层次结构、计算复杂性等。每节后面都给出了习题，并包含部分习题的解答，方便教学。