计算机科学与技术学科前沿丛书 形式语言与自动机

第1章 计算理论基础 1

1.1 集合的基本概念 1

1.1.1 集合的定义 1

1.1.2 集合的表示 1

1.1.3 集合间的关系 1

1.1.4 集合的运算 2

1.2 关系 3

1.2.1 二元关系 3

1.2.2 二元关系的性质 3

1.2.3 等价关系 3

1.2.4 递归定义与归纳证明 4

1.3 图与树 6

1.3.1 无向图 7

1.3.2 有向图 7

1.3.3 树 8

1.3.4 二叉树 8

1.4 三个重要概念 9

习题 10

第2章 文法与语言 13

2.1 启示 13

2.2 文法的形式定义 14

2.3 文法的构造 15

2.4 文法的Chomsky体系 16

习题 18

第3章 上下文无关文法及其语言 20

3.1 上下文无关文法 20

3.1.1 派生与派生树 20

3.1.2 文法的二义性 23

3.2 文法和语言的讨论 24

3.3 句法分析 27

3.3.1 最左派生和不确定性 27

3.3.2 文法图 28

3.3.3 广度优先自顶向下句法分析 29

3.3.4 深度优先自顶向下分析 30

3.3.5 自底向上分析 32

3.4 上下文无关文法的化简 38

3.4.1 无用符号 38

3.4.2 消除ε产生式 38

3.4.3 消除单一产生式 39

3.4.4 消除左递归 40

3.5 Chomsky范式 44

3.6 Greibach范式 46

习题 48

第4章 有穷状态自动机 54

4.1 语言的识别 54

4.2 有穷状态自动机的形式定义 55

4.3 确定的有穷自动机 55

4.4 状态转换图 57

4.5 不确定的有穷自动机 58

4.6 NFA与DFA的等价 60

4.7 带空转移的NFA 63

4.8 ε-NFA的确定化 65

4.9 DFA最小化 66

习题 70

第5章 正则语言和正则文法 73

5.1 正则表达式 73

5.1.1 正则表达式的定义 73

5.1.2 正则语言 73

5.2 有穷自动机和正则语言 74

5.2.1 正则表达式到有穷自动机 74

5.2.2 有穷自动机到正则表达式 76

5.3 正则文法和有穷自动机 78

5.3.1 正则文法 78

5.3.2 正则文法与NFA 81

习题 85

第6章 正则语言的性质 87

6.1 正则语言的封闭性 87

6.1.1 简单运算的封闭性 87

6.1.2 其他运算的封闭性 88

6.2 非正则语言的识别 91

6.2.1 鸽巢原理 92

6.2.2 泵引理 92

6.3 Myhill Nerode定理 94

6.4 正则语言的判定算法 99

习题 100

第7章 下推自动机与上下文无关文法 101

7.1 非确定型下推自动机 101

7.1.1 下推自动机的定义 101

7.1.2 下推自动机接受的语言 102

7.2 下推自动机与上下文无关文法 104

7.2.1 上下文无关语言相应的下推自动机 104

7.2.2 下推自动机与相应的上下文无关文法 106

7.3 确定型下推自动机 109

7.4 双栈自动机 110

习题 111

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

8.1 上下文无关文法的泵引理 114

8.2 上下文无关语言的封闭性 116

8.3 上下文无关语言的可判定性 118

习题 118

第9章 图灵机 120

9.1 标准图灵机 120

9.1.1 图灵机的形式定义 120

9.1.2 图灵机识别器 122

9.1.3 图灵机转换器 124

9.2 完成复杂任务的图灵机 126

习题 128

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

10.1 带不动选择图灵机 130

10.2 多道图灵机 131

10.3 单向无穷带图灵机 132

10.4 离线图灵机 133

10.5 多带图灵机 134

10.6 多头图灵机 137

10.7 非确定型图灵机 138

10.8 线性界限自动机 140

习题 141

第11章 其他计算模型 143

11.1 递归函数 143

11.1.1 递归函数 143

11.1.2 递归函数的扩展理解 146

11.2 波斯特系统 148

11.3 重写系统 149

11.3.1 矩阵文法 149

11.3.2 马尔可夫算法 150

习题 151

参考文献 152