《形式语言及其与自动机的关系》求取 ⇩

译者序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