形式语言与自动机PDF|Epub|txt|kindle电子书版本网盘下载

形式语言与自动机PDF格式电子书版下载

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

第1章 预备知识1

1.1定理及其证明方法1

演绎法2

反证法3

归纳法5

1.2集合及其基本运算7

集合基础知识7

集合的基本运算8

关系与映射9

1.3图和树简介11

图的基本概念12

图的矩阵表示13

树的基本知识15

1.4字母表、字符串和语言16

习题18

第2章 文法的一般理论21

2.1问题的提出21

2.2形式文法与形式语言23

2.3文法的乔姆斯基分类30

习题40

第3章 有穷自动机42

3.1非形式化描述42

3.2有穷自动机的基本定义44

3.3非确定的有穷自动机48

3.4具有ε转移的有穷自动机52

3.5有穷自动机的应用55

在文本中查找字符串55

用于文本搜索的非确定的有穷自动机55

识别关键字集合的DFA56

3.6具有输出的有穷自动机58

习题60

第4章 正则表达式63

4.1正则表达式的定义63

4.2正则表达式和有穷自动机的关系65

4.3正则表达式的等价变换70

交换律与结合律70

单位元与零元71

分配律71

与“＊”构造有关的定律72

发现正则表达式定律的一般方法73

4.4正则表达式的应用75

UNIX中的正则表达式75

词法分析76

查找文本中的模式77

习题78

第5章 正则语言的性质80

5.1正则文法和有穷自动机的关系80

5.2正则语言的泵引理82

5.3正则语言的封闭性85

5.4正则语言的判定算法89

5.5有穷自动机的最小化91

习题99

第6章 上下文无关文法101

6.1上下文无关文法的语法分析101

6.2上下文无关文法的化简107

6.3上下文无关文法的范式111

6.4上下文无关文法的应用115

用上下文无关文法描述语言115

语法分析器生成工具YACC116

标记语言117

XML和文档类型定义118

习题121

第7章 下推自动机124

7.1下推自动机的定义124

7.2下推自动机接受的语言125

7.3下推自动机和上下文无关文法的关系130

7.4确定的下推自动机134

习题135

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

8.1上下文无关语言的泵引理136

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

8.3上下文无关语言的判定算法142

习题146

第9章 图灵机导引148

9.1图灵机的基本模型148

9.2图灵机的程序设计技术154

在状态中存储符号154

多道技术155

子程序技术159

9.3图灵机的变形161

双向无限带161

多带162

非确定的图灵机165

双栈机166

作为枚举器的图灵机167

9.4图灵机与计算机169

用计算机模拟图灵机169

用图灵机模拟计算机170

比较计算机与图灵机的运行时间172

9.5图灵机与0型文法的关系173

习题176

第10章 不可判定性178

10.1递归集和递归可枚举集的性质178

10.2通用图灵机和第一个不可判定问题180

10.3归约方法和莱斯定理183

10.4关于上下文无关语言的不可判定问题188

10.5波斯特对应问题的不可判定性及其应用191

习题197

第11章 线性有界自动机和上下文有关文法199

11.1线性有界自动机199

11.2线性有界自动机和上下文有关文法的关系201

11.3上下文有关语言的性质及其与递归集的关系202

11.4各语言类之间的关系204

习题205

第12章 确定的上下文无关语言和LR（k）文法206

12.1确定的下推自动机的标准形式206

12.2确定的上下文无关语言的性质207

12.3 LR（0）文法212

12.4 LR（0）文法与DPDA的关系216

12.5 LR（k）文法221

习题226

参考文献228