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

目录 1

第1章 预备知识 1

1.1 集合及其运算 1

1.2 证明和证明方法 7

1.3 字母表、字符串和语言 12

习题 14

第2章 文法理论 17

2.1 问题的提出 17

2.2 文法的形式定义及分类 20

2.3 文法的几个有关概念 29

习题 42

第3章 有穷自动机和正规表达式 45

3.1 有穷自动机的背景和基本定义 45

3.2 非确定的有穷自动机 50

3.3 具有ε动作的有穷自动机 56

3.4 正规表达式和正规集 61

3.5 具有输出的有穷自动机 71

习题 75

第4章 正规文法与正规集的性质 79

4.1 正规文法与有穷自动机的关系 79

4.2 正规集的缩胀定理 82

4.3 正规集的封闭性质与判定算法 87

4.4 有穷自动机的极小化 92

习题 106

第5章 上下文无关文法与下推自动机 109

5.1 上下文无关文法的化简 109

5.2 上下文无关文法的范式 116

5.3 下推自动机 122

5.4 下推自动机与上下文无关文法的关系 129

习题 134

6.1 上下文无关语言的缩胀定理 136

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

6.2 上下文无关语言的封闭性质 145

6.3 上下文无关语言的判定算法 148

习题 154

第7章 图灵机 156

7.1 图灵机的基本模型 156

7.2 图灵机的构造技术 164

7.3 图灵机的变型 174

7.4 图灵机与0型文法的关系 185

习题 189

第8章 不可判定性 191

8.1 递归集和递归可枚举集的性质 192

8.2 通用图灵机和两个不可判定问题 195

8.3 归约方法和Rice定理 200

8.4 关于CFL的不可判定问题 207

8.5 Post对应问题的不可判定性及其应用 213

习题 220

第9章 线性有界自动机和上下文有关语言 223

9.1 线性有界自动机 223

9.2 线性有界自动机和上下文有关文法的关系 225

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

9.4 语言类之间的关系 231

习题 233

第10章 确定的下推自动机与LR(k)文法 234

10.1 确定的下推自动机及其标准形式 234

10.2 确定的上下文无关语言的性质 237

10.3 LR(O)文法 245

10.4 LR(O)文法与DPDA的关系 252

10.5 LR(k)文法 261

习题 271

参考文献 273