有限自动机理论2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载

有限自动机理论PDF格式电子书版下载

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

第1章 基础知识1

1.1 集合及其运算3

1.2 关系5

1.2.1 二元关系5

1.2.2 等价关系5

1.2.3 关系的合成6

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 形式语言与自动机的发展13

习题114

第2章 形式语言简介16

2.1 例子语言16

2.2 文法和语言的关系21

2.2.1 文法21

2.2.2 语言23

2.2.3 文法和语言的3类问题24

2.3 Chomsky对文法和语言的分类25

2.4 文法产生语言30

2.5 无用非终结符38

2.6 推导树39

2.7 空串定理41

2.8 消除左递归42

2.8.1 消除直接左递归42

2.8.2 消除间接左递归43

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

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

2.10.1 语言之间的基本运算46

2.10.2 语言之间的运算的封闭性47

2.10.3 语言之间的其他运算52

2.11 正则表达式和正则集54

习题256

第3章 有限状态自动机59

3.1 有限状态自动机59

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

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

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

3.4.1 不确定的有限状态自动机78

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

3.5 带有ε动作的有限状态自动机85

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

3.6.1 双向的有限状态自动机92

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

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

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

习题3111

第4章 正则语言112

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

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

4.1.2 正则语言的等价模型122

4.2 正则语言的泵浦引理124

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

习题4132

第5章 下推自动机134

5.1 下推自动机134

5.1.1 确定的下推自动机135

5.1.2 不确定的下推自动机138

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

5.1.4 广义下推自动机和单态下推自动机144

5.2 上下文无关文法和范式146

5.2.1 Chomsky范式147

5.2.2 Greibach范式148

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

5.4 下推自动机应用实例162

习题5164

第6章 图灵机166

6.1 图灵机的基本模型166

6.1.1 图灵机的定义166

6.1.2 图灵机的构造169

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

6.3 图灵机的构造技术177

6.3.1 图灵机的存储技术178

6.3.2 图灵机的移动技术181

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

6.3.4 图灵机的多道技术194

6.3.5 图灵机的查讫技术200

6.3.6 图灵机的子程序技术201

6.4 图灵机变形204

6.4.1 双向无穷带图灵机205

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

6.4.3 不确定图灵机209

6.4.4 多维图灵机211

6.4.5 其他图灵机212

6.5 通用图灵机215

6.5.1 编码的目的215

6.5.2 编码方法215

6.5.3 总结218

6.6 图灵机与短语结构语言218

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

6.8 图灵机应用实例219

习题6225

参考文献227