《上下文无关语言的数学理论》

序言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