第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