计算机科学与技术学科前沿丛书 形式语言与自动机PDF|Epub|txt|kindle电子书版本网盘下载

计算机科学与技术学科前沿丛书 形式语言与自动机PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第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 带空转移的NFA63

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 正则文法与NFA81

习题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