语言与机器

出版者的话

专家指导委员会

译者序

前言

绪论

第一部分基础

第1章数学预备知识

1.1集合论

1.2笛卡儿积、关系和函数

1.3等价关系

1.4可数集合和不可数集合

1.5对角化和自反

1.6递归定义

1.7数学归纳

1.8有向图

1.9练习

参考文献注释

第2章语言

2.1字符串和语言

2.2语言的有穷规格说明

2.3正则集合和表达式

2.4正则表达式和文本搜索

2.5练习

参考文献注释

第二部分文法、自动机和语言

第3章上下文无关文法

3.1上下文无关文法和语言

3.2文法和语言的例子

3.3正则文法

3.4验证文法

3.5最左推导和二义性

3.6上下文无关文法和编程语言定义

3.7练习

参考文献注释

第4章上下文无关文法范式

4.1文法转换

4.2消去入规则

4.3去掉链规则

4.4无用符

4.5乔姆斯基范式

4.6CYK算法

4.7去掉直接左递归

4.8格立巴赫范式

4.9练习

参考文献注释

第5章有限自动机

5.1一个有限状态自动机

5.2确定型有限自动机

5.3状态图和例子

5.4非确定型有限自动机

5.5λ-转换

5.6去掉非确定性

5.7DFA的最小化

5.8练习

参考文献注释

第6章正则语言的性质

6.1有限状态机接收正则语言

6.2表达式图

6.3正则文法和有限自动机

6.4正则语言的封闭性质

6.5非正则语言

6.6规则语言的泵引理

6.7Myhill-Nerode定理

6.8练习

参考文献注释

第7章下推自动机和上下文无关语言

7.1下推自动机

7.2PDA的变种

7.3上下文无关语言的接收

7.4上下文无关语言的泵引理

7.5上下文无关语言的封闭性

7.6练习

参考文献注释

第三部分可计算性

第8章图灵机

8.1标准图灵机

8.2作为语言接收器的图灵机

8.3可供选择接收标准

8.4多道图灵机

8.5双向图灵机

8.6多带图灵机

8.7非确定型图灵机

8.8用来枚举语言的图灵机

8.9练习

参考文献注释

第9章图灵可计算函数

9.1函数的计算

9.2数值计算

9.3图灵机的顺序操作

9.4函数的合成

9.5不可计算函数

9.6关于编程语言

9.7练习

参考文献注释

第10章乔姆斯基层次

10.1无限制文法

10.2上下文有关文法

10.3线性有界自动机

10.4乔姆斯基层次

10.5练习

参考文献注释

第11章判定问题与丘奇图灵论题

11.1判定问题的描述

11.2判定问题和递归语言

11.3问题归约

11.4丘奇图灵论题

11.5通用机

11.6练习

参考文献注释

第12章不可判定性

12.1图灵机的停机问题

12.2问题归约和不可判定性

12.3其他的停机问题

12.4莱斯定理

12.5不可解决的词问题

12.6波斯特对应问题

12.7上下文无关文法中的不可判定问题

12.8练习

参考文献注释

第13章Mu-递归函数

13.1原始递归函数

13.2一些原始递归函数

13.3有界操作符

13.4除法函数

13.5歌德尔数字和串值递归

13.6可计算部分函数

13.7图灵可计算函数和Mu-递归函数

13.8修订的丘奇图灵论题

13.9练习

参考文献注释

第四部分计算复杂性

第14章时间复杂性

14.1复杂性度量

14.2增长的速度

14.3图灵机的时问复杂性

14.4复杂性和图灵机的变种

14.5线性加速

14.6语言时间复杂性的属性

14.7计算机计算的模拟

14.8练习

参考文献注释

第15章P、NP和库克定理

15.1非确定型图灵机的时间复杂性

15.2P类和NP类

15.3问题表示和复杂性

15.4判定问题和复杂性类

15.5哈密尔顿回路问题

15.6多项式时间归约

15.7P=NP？

15.8可满足性问题

15.9复杂类的关系

15.10练习

参考文献注释

第16章NP-完全问题

16.1归约和NP-完全问题

16.2三元可满足性问题

16.3三元可满足性的归约

16.4归约和子问题

16.5最优化问题

16.6近似算法

16.7近似方案

16.8练习

参考文献注释

第17章其他复杂性类

17.1派生的复杂性类

17.2空间复杂性

17.3空间复杂性和时间复杂性的关系

17.4P-空间，NP-空间和萨维奇定理

17.5P-空间完全性

17.6一个难解问题

17.7练习

参考文献注释

第五部分确定型语法分析

第18章语法分析引论

18.1文法图

18.2自顶向下语法分析

18.3归约和自底向上语法分析

18.4自底向上语法分析器

18.5语法分析和编译

18.6练习

参考文献注释

第19章LL(k)文法

19.1上下文无关文法中的预读

19.2FIRST集合、FOLLOW集合和预读集合

19.3强LL(k)语法

19.4FIRSTk集合的构造

19.5FOLLOWk集合的构造

19.6强LL(1)文法

19.7强LL(k)分析器

19.8LL(k)文法

19.9练习

参考文献注释

第20章LR(k)文法

20.1LR(0)上下文

20.2LR(0)分析器

20.3LR(0)机

20.4被LR(0)机接收

20.5LR(1)文法

20.6练习

参考文献注释

附录Ⅰ标记索引

附录Ⅱ希腊字母表

附录ⅢASCⅡ字符集

附录ⅢJava的BNF范式定义

参考文献

索引

　　理论计算机科学是推动计算机技术和应用向前发展的巨大动力。形式语言、自动机、可计算性、计算复杂性和相关方面内容构成的计算理论，是理论计算机科学的基础内容之一。本书由美国莱特州立大学计算机科学及工程系的ThomasA.Sudkamp教授编写，是介绍这些内容的优秀教材。全书不仅介绍了计算机科学的基础，探讨了算法计算的能力和局限；而且还通过概念的严格表述，以及使用通俗的例子来解释定理，从而帮助学生提高数学论证能力。书中每章后面都有一些练习，通过这些练习使学生加深对本章内容的理解。　　本书是计算理论方面的优秀教材之一，包括上下文无关文法、上下文无关文法范式、有限自动机、正则语言的性质、下推自动机和上下文无关语言、图灵机、图灵可计算函数、乔姆斯基层次、判定问题与丘奇图灵机、不可判定性、Mu-递归函数、时间复杂性、库克定理、NP-完全问题、LL(k)文法以及LR(k)文法等问题。本书不仅介绍了计算机科学的基础，而且通过概念的严格表述，以及使用通俗的例子来阐释定理，从而帮助学生提高数学论证能力以及对计算理论知识的全面深入的理解。书中每章后面都有附有大量习题，通过完成这些习题，学生可以加深对本章内容的理解。　　本书可以用作计算机科学、计算机工程及其相关专业的教材，也可以作为从事计算理论、形式语言以及计算机系统研发的研究人员和工程技术人员的参考书。