形式语言及其与自动机的关系PDF电子书下载

译者序 1

第一章 语言及其表示法 1

1.1 字母表和语言 1

1.2 过程和算法 2

原序 3

1.3 语言的表示 6

习题 8

第二章 文法 10

2.1 启示 10

2.2 文法的形式概念 12

2.3 文法的类型 16

2.4 空句子 19

2.5 前后文有关文法的递归性 22

2.6 前后文无关文法的派生树 24

习题 32

本章参考文献 33

第三章 有穷自动机和正规文法 34

3.1 有穷自动机 34

3.2 等价关系和有穷自动机 36

3.3 不确定的有穷自动机 39

3.4 有穷自动机和3型语言 44

3.5 3型语言的性质 47

3.6 关于有穷自动机的可解问题 53

3.7 双向有穷自动机 55

习题 60

本章参考文献 61

第四章 前后文无关文法 62

4.1 前后文无关文法的简化 62

4.2 Chomsky范式 68

4.3 Greibach范式 71

4.4 有穷性的可解性和“uvwxy定理” 76

4.5 自嵌套特性 82

4.6 前后文无关文法中的б规则 83

4.7 前后文无关语言和文法的特殊类型 85

习题 87

本章参考文献 89

第五章 下推自动机 91

5.1 非形式的描述 91

5.2 定义 93

5.3 不确定的下推自动机和前后文无关语言 99

习题 105

本章参考文献 106

6.2 定义和记号 107

第六章 图灵机 107

6.1 引言 107

6.3 图灵机的构造技术 111

6.4 图灵机作为过程 121

6.5 图灵机的修改 123

6.6 等价于基本模型的受限图灵机 131

习题 134

本章参考文献 135

第七章 图灵机：停机问题 0型语言 136

7.1 非形式的讨论 136

7.2 通用图灵机 136

7.3 停机问题的不可解性 142

7.4 递归集类 144

7.5 图灵机和0型文法 145

习题 149

本章参考文献 150

第八章 线性界限自动机与前后文有关语言 151

8.1 引言 151

8.2 线性界限自动机与前后文有关语言的关系 152

8.3 前后文有关语言是递归集的子类 154

习题 155

本章参考文献 156

第九章 对语言的运算 157

9.1 引言 157

9.2 对基本运算的封闭性 157

9.3 对映射的封闭性 162

习题 174

本章参考文献 175

10.2 定义 177

10.1 引言 177

第十章 时间界限和带界限的图灵机 177

10.3 “加速”定理和“缩带”定理 179

10.4 单带图灵机和交叉序列 187

10.5 带复杂度的下界 192

10.6 带谱系和时间谱系 196

习题 202

本章参考文献 203

第十一章 识别前后文无关语言时的时空界限 204

11.1 引言 204

11.2 识别前后文无关语言时的时间要求 204

11.3 识别前后文无关语言时的空间要求 210

习题 215

本章参考文献 216

12.1 引言 217

第十二章 确定的下推自动机 217

12.2 确定的语言的补集 218

12.3 确定的语言的性质 224

12.4 不确定的前后文无关语言 235

12.5 LR(k)文法 236

习题 245

本章参考文献 246

第十三章 堆栈自动机 247

13.1 定义 247

13.2 堆栈自动机的受限型 251

13.3 双向堆栈自动机的力量 252

13.4 单向堆栈自动机的力量 263

13.5 堆栈自动机的递归性 271

13.6 封闭性 272

本章参考文献 274

习题 274

第十四章 可判定性 275

14.1 可解的和不可解的问题 275

14.2 Post的对应问题 276

14.3 有关前后文有关语言的一个问题 285

14.4 前后文无关语言的不可解的问题 286

14.5 前后文无关语言的歧义性 289

14.6 有关确定的前后文无关语言的不可解的问题 300

14.7 对正规文法、LR(k)文法、前后文无关文法、前后文有关文法和0型文法的不可解性的总结 301

习题 302

本章参考文献 303

参考文献 304

汉英名词对照 310