上下文无关语言的数学理论PDF电子书下载

序言 1

预备知识 1

第一章：上下文无关与类ALGOL语言 1

1.1 短语结构语言 1

1.2 类ALGOL语言 9

1.3 等价性 12

1.4 辅助引理 17

1.5 派生树 23

1.6 岐义性 31

1.7 置换 39

1.8 ε无关文法 42

1.9 历史参考资料 51

2.1 有穷状态接受器和正规集合 52

第二章：接受器和语言 52

2.2 线性生成式 58

2.3 一类特殊形式的语言 63

2.4 下推接受器 68

2.5 描述 73

2.6 确定的语言 89

2.7 历史参考资料 101

第三章 运算 102

3.1 非语言 102

3.2 交和差 107

3.3 时序转换器映射 111

3.4 Gsm映射的描述 120

3.5 下推转换器 127

3.6 特殊运算 131

3.7 同态描述 137

3.8 历史参考资料 143

第四章：可判定性 144

4.1 可解性结果 145

4.2 基本的不可判定问题 148

4.3 Gsm映射 161

4.4 Pdt映射 169

4.5 岐义性 174

4.6 历史参考资料 176

第五章：有界语言 177

5.1 基本术语 177

5.2 Parikh定理 182

5.3 结构 187

5.4 描述 198

5.5 识别 212

5.6 其他判定问题 220

5.7 历史参考资料 230

第六章：先天岐义性 231

6.1 a1*...an*中的先天岐义语言 231

6.2 有界先天岐义语言 246

6.3 判定程序 260

6.4 历史参考资料 264

附录：定理5.6.2的证明 265

参考文献和有关文章 274

索引： 287

符号 287

作者 288

主题 290