第1章 基础知识/1

 1.1 集合及其运算/2

 1.2 关系/4

1.2.1 二元关系/4

1.2.2 等价关系/5

1.2.3 关系的合成/5

 1.3 证明和证明的方法/7

1.3.1 反证法/7

1.3.2 归纳法/8

1.3.3 递归的定义与归纳证明/8

 1.4 图与树/9

 1.5 语言/10

 1.6 常用术语/10

 1.7 形式语言与自动机的发展/12

 习题1/14

第2章 形式语言简介/15

 2.1 例子语言/15

 2.2 文法和语言的关系/20

2.2.1 文法/20

2.2.2 语言/22

2.2.3 文法和语言的3类问题/23

 2.3 Chomsky对文法和语言的分类/24

 2.4 文法产生语言/29

 2.5 无用非终结符/37

 2.6 推导树/38

 2.7 空串定理/40

 2.8 消除左递归/41

2.8.1 消除直接左递归/41

2.8.2 消除间接左递归/42

 2.9 上下文无关文法的另一种表示/44

 2.10 语言之间的运算及运算的封闭性/45

2.10.1 语言之间的基本运算/45

2.10.2 语言之间的运算的封闭性/46

2.10.3 语言之间的其他运算/51

 2.11 正则表达式和正则集/53

 习题2/56

第3章 有限状态自动机/58

 3.1 有限状态自动机/58

 3.2 确定的有限状态自动机接收的语言/60

 3.3 确定的有限状态自动机接收语言的例子/65

 3.4 不确定的有限状态自动机/77

3.4.1 不确定的有限状态自动机的概念/77

3.4.2 不确定的有限状态自动机的确定化/79

 3.5 带有 动作的有限状态自动机/84

 3.6 有限状态自动机的一些变形/91

3.6.1 双向的有限状态自动机/91

3.6.2 带有输出的有限状态自动机/92

 3.7 有限状态接收机的存储技术/95

 3.8 有限状态自动机应用实例/97

 习题3/103

第4章 正则语言/105

 4.1 正则语言与有限状态自动机/105

4.1.1 正则表达式对应有限状态自动机/105

4.1.2 正则语言的等价模型/115

 4.2 正则语言的泵浦引理/117

 4.3 正则语言类中的判定算法/124

 习题4/125

第5章 下推自动机/127

 5.1 下推自动机/127

5.1.1 确定的下推自动机/128

5.1.2 不确定的下推自动机/131

5.1.3 下推自动机接收语言的两种方式/133

5.1.4 广义下推自动机和单态下推自动机/137

 5.2 上下文无关文法和范式/139

5.2.1 Chomsky范式/140

5.2.2 Greibach范式/141

 5.3 下推自动机与上下文无关语言/143

 5.4 下推自动机应用实例/155

 习题5/157

第6章 图灵机/159

 6.1 图灵机的基本模型/159

6.1.1 图灵机的定义/159

6.1.2 图灵机的构造/162

 6.2 图灵机作为非负整数函数计算模型/167

 6.3 图灵机的构造技术/170

6.3.1 图灵机的存储技术/171

6.3.2 图灵机的移动技术/174

6.3.3 图灵机扫描多个符号技术/176

6.3.4 图灵机的多道技术/187

6.3.5 图灵机的查讫技术/191

6.3.6 图灵机的子程序技术/192

 6.4 图灵机变形/195

6.4.1 双向无穷带图灵机/195

6.4.2 多带多读/写头图灵机/198

6.4.3 不确定图灵机/200

6.4.4 多维图灵机/202

6.4.5 其他图灵机/202

 6.5 通用图灵机/205

6.5.1 编码的目的/205

6.5.2 编码方法/206

6.5.3 总结/208

 6.6 图灵机与短语结构语言/209

 6.7 线性有界的图灵机与上下文相关语言/209

 6.8 图灵机应用实例/209

 习题6/214

第7章 量子自动机/216

 7.1 量子有限自动机/219

7.1.1 Moore ＆ Crutchfield量子有限自动机的定义/219

7.1.2 Moore ＆ Crutchfield量子有限自动机所识别的语言/220

7.1.3 Moore ＆ Crutchfield量子正规语言的性质/221

7.1.4 Kondacs ＆ Watrous量子有限自动机的定义/221

7.1.5 Kondacs ＆ Watrous量子有限自动机的例子/223

7.1.6 量子有限自动机模型的研究进展概述/224

 7.2 量子下推自动机/226

7.2.1 Moore ＆ Crutchfield量子下推自动机的定义/226

7.2.2 Moore ＆ Crutchfield量子文法的定义/226

7.2.3 Moore ＆ Crutchfield量子下推自动机所识别的语言/227

7.2.4 Moore ＆ Crutchfield量子下推自动机所识别的语言的代数性质/227

7.2.5 其他类型的量子下推自动机/228

7.2.6 量子下推自动机模型的研究进展概述/231

 7.3 量子图灵机/232

7.3.1 量子图灵机的提出/232

7.3.2 Church-Turing-Deutsch原理/232

7.3.3 Bernstein ＆ Vazirani量子图灵机/233

7.3.4 量子图灵机模型与量子电路模型的等价：Yao定理/234

7.3.5 Gudder量子图灵机/234

7.3.6 量子图灵机模型的研究进展概述/236

参考文献/238

陈文宇、田玲、程伟、刘贵松编著的《有限自动机理论(第2版)》由“电子科技大学‘十二五’规划研究生教材建议基金”资助出版。本书简述形式语言的基本内容，包括文法的分类和语言间运算的封闭性；系统地论述有限自动机：有限状态自动机、下推自动机和图灵机(包括量子图灵机)的基础理论：从构造文法产生语言的角度和构造自动机识别语言的角度对语言进行讨论；介绍文法与等价的自动机之间的转换方法；并介绍有限自动机的一些典型应用。本书以新的思维方式为读者提供了一把钥匙，主要培养读者的独立思考能力，使用符号化的系统描述程序设计语言或自然语言的语法结构的能力，以及构造自动机的能力。

《有限自动机理论(第2版)》可作为高等学校计算机科学与技术学科各专业研究生的教材或参考书，也可作为计算机应用领域广大科技人员的参考书。

陈文宇、田玲、程伟、刘贵松编著的《有限自动机理论(第2版)》共分为7章。第1章回顾本书所需的基本数学知识；第2章是形式语言的基本内容，包括文法的定义、分类，文法的构造方法，以及语言之间的运算的封闭性的讨论；第3章、第4章介绍有限状态自动机的构造方法及其对应的正则语言的性质；第5章介绍下推自动机；第6章是对图灵机的讨论；第7章介绍量子图灵机。

本书的目标是，力求使计算机科学与技术学科各个专业的研究生掌握各类有限自动机的模型、构造方法和技巧，培养计算思维能力。

本书基本覆盖了形式语言的基本内容和有限自动机的主要内容，可以作为计算机科学与技术学科各专业研究生的教材。