《形式语言与自动机》求取 ⇩

目录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