译者序

第一章 语言及其表示法

1.1 字母表和语言

1.2 过程和算法

原序

1.3 语言的表示

习题

第二章 文法

2.1 启示

2.2 文法的形式概念

2.3 文法的类型

2.4 空句子

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

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

习题

本章参考文献

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

3.1 有穷自动机

3.2 等价关系和有穷自动机

3.3 不确定的有穷自动机

3.4 有穷自动机和3型语言

3.5 3型语言的性质

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

3.7 双向有穷自动机

习题

本章参考文献

第四章 前后文无关文法

4.1 前后文无关文法的简化

4.2 Chomsky范式

4.3 Greibach范式

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

4.5 自嵌套特性

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

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

习题

本章参考文献

第五章 下推自动机

5.1 非形式的描述

5.2 定义

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

习题

本章参考文献

6.2 定义和记号

第六章 图灵机

6.1 引言

6.3 图灵机的构造技术

6.4 图灵机作为过程

6.5 图灵机的修改

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

习题

本章参考文献

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

7.1 非形式的讨论

7.2 通用图灵机

7.3 停机问题的不可解性

7.4 递归集类

7.5 图灵机和0型文法

习题

本章参考文献

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

8.1 引言

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

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

习题

本章参考文献

第九章 对语言的运算

9.1 引言

9.2 对基本运算的封闭性

9.3 对映射的封闭性

习题

本章参考文献

10.2 定义

10.1 引言

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

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

10.4 单带图灵机和交叉序列

10.5 带复杂度的下界

10.6 带谱系和时间谱系

习题

本章参考文献

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

11.1 引言

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

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

习题

本章参考文献

12.1 引言

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

12.2 确定的语言的补集

12.3 确定的语言的性质

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

12.5 LR(k)文法

习题

本章参考文献

第十三章 堆栈自动机

13.1 定义

13.2 堆栈自动机的受限型

13.3 双向堆栈自动机的力量

13.4 单向堆栈自动机的力量

13.5 堆栈自动机的递归性

13.6 封闭性

本章参考文献

习题

第十四章 可判定性

14.1 可解的和不可解的问题

14.2 Post的对应问题

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

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

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

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

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

习题

本章参考文献

参考文献

汉英名词对照