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

识别关键字集合的DFA 56

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

语法分析器生成工具YACC 116

标记语言 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