本书作为《形式语言与自动机理论（第3版）》（主教材）的配套教学辅导用书，按照主教材的结构编写而成。本书包括有关内容的讲解、学习要点、问题分析、求解思路和方法、注意事项。考虑到该课程习题求解具有相当的难度，以及给出全部习题解答又不利于学生学习，只给出了典型习题的解析。为了引导读者及时总结学习内容，按照小节给出知识点和主要内容解读，为读者学习和掌握主教材中的知识点和问题求解方法，体会问题求解的核心思想提供帮助，对教师和学生来说，阅读这些内容都是很有意义的。

第3版FOREWORD培养创新人才，对本科教育来讲，主要是夯实基础、训练思维、养成探索之习惯。所以，创新能力（innovation ability）的培养不能着眼于眼前，简单追求立竿见影，必须面向未来，寻求可持续发展。所以，要追求雄厚的基础(fundaments)、有效的思维（thinking）、勤奋的实践（practice），这3点简单归纳为“厚基础、善思维、常实践”，可以用如下公式表示：I=F+T+P

首先是“厚基础”，包括知识基础和能力基础。对计算机类专业人才来说，重要的理论基础主要来自于理论课程的学习。认真深入地读几本基础性的书，深入理解其中的内容，使自己的思想水平上升到一个新的高度，是非常必要的。为了达到学习知识以提升能力的目的，就要在学习知识的同时，注重对其中蕴含的思想和方法的学习，培养主动探索意识与精神。其次是“善思维”。古人云：“学而不思则罔，思而不学则殆。”要想将书中的知识转化成自己的知识和能力，就必须在认真读书的过程中勤奋地思考。在培养创新思维能力的过程中建立创新意识，形成创新能力。最后，“常实践”是手段。在实践中去加深理解，实践探索。“动手能力”不能是狭义的，它不仅仅简单地来自于下工厂、进企业、进实验室的活动，更不是简单地“编程序”。作为一名科技工作者，“动手”的关键在于“动脑”。

就计算学科而言，离开了理论的指导，就很难有高水平的实践。作者认为，“理论，可以使人‘站到巨人的肩膀上’，并拥有一个‘智慧的脑’”；“实践，需要用智慧的脑，练就一双灵巧的手，去开创一个新世界”。不应该将理论和实践教学割裂开，要有意识地将它们融在一起，这样会收到事半功倍的效果。这就是说，既要“动手”又要“动脑”，要用高水平的动脑，去“指挥”高水平的动手，也就是“理性实践”。而且，不同的专业、不同的课程需要不同形式的实践。就本课程而言，认真地读书，思考一些问题，做一些各种难度的练习，就是一种常规的实践。在这个过程中领悟大师们的思维，从而达到训练思维、提升思维水平的目的，不断强化自己探索未知的意识，提升探索的能力。

这些能力导向教育的思想如何体现在教材中？如何引导读者去发现问题、分析问题、解决问题？如何使得这些引导既深入又简单？它们一直是作者努力探讨的问题。在本书的写作中，除了叙述基本的知识内容外，还努力进行着问题的分析，从而使这些分析在本书中占有很大的篇幅。建议读者不要简单地背定义、定理，要深入地理解，达到能够用自己的语言表达它们的程度。特别要注意认真地阅读分析部分，其中的某一句话可能会使读者产生“恍然大悟”之感，而某一句话可能会引导读者思考更深入的问题。希望读者能够仔细地阅读这些内容，相信会有更多的收获。

本套书自2003年1月出版以来，其第1版在2004年获北京市高等教育教学成果一等奖，2005年被评为北京市精品教材。该套书的第2版是普通高等教育“十一五”国家级规划教材，2008年被评为国家级普通高等教育精品教材。本版作为普通高等教育“十二五”国家级规划教材出版。作者看到，10年来，该教材一直受到读者的欢迎和鼓励，开设此课程的学校很多将其选为教材，使得该套教材成为国内同类教材中发行量和影响力最大的精品教材。另外，清华大学出版社对本套教材的建设，给予了很大的支持，特别是本书的责任编辑张瑞庆编审发挥了重要作用。在此，我们一并表示真诚的感谢。我们相信，随着计算机专业教育的发展，在大家的支持下，该课程在高水平人才的培养中将会进一步发挥作用。

对书中的错误，请读者不吝赐教。

作者2013年2月

第2版FOREWORD

“离散数学”和“形式语言与自动机理论”是计算机科学与技术专业本科两大专业基础理论课程，这两门课程不仅为学生提供本专业的基础知识，更肩负着培养学生计算思维能力的重要任务。在形式语言与自动机理论中，按照类研究问题的描述，并研究这些描述之间的关系、变换等，从而将问题的求解从实例计算推进到类计算和模型计算，这正是计算学科所追求的，也是本学科的工作者解决问题的着眼点和方法，以及所构建的系统的最大特点和优势。随着计算学科本科生和研究生教育的不断发展，这种优势将进一步的凸现。

从2002年到2003年，作者以近20年教学积累和相应的教案为基础，辅以10余年对教育教学的思考撰写成了《形式语言与自动机理论》和配套的《形式语言与自动机理论教学参考书》，这套书出版后，受到了广大读者的欢迎，一些相识的和不相识的读者对该书给予了充分的肯定，被选作本科生和研究生教材，成为国内相应课程发行最广的教材。2004年这套书被评为北京市精品教材，并且荣获2004年北京市高等教育教学成果一等奖，2006年被评为教育部普通高等教育“十一五”国家级规划教材。

在这次修订中，又融进了近几年来作者在从事相关课程教学以及计算机科学与技术专业优秀教材建设中所获得的经验和体会。例如，进一步强调教材是写给读者的，不是写给自己的。而且强调教材的写作特征，认为在这些读者中，首先是写给学生，要考虑他们是初学者，不同类型的学生有不同的关注点，更需要强调用词和描述的准确性、一致性，语言表达的清晰性和叙述的完整性，杜绝陌生名词的突然出现和使用；其次是教师，面对他们，要考虑对现代教育思想的体现和课程的容量；第三是普通的读者，需要通俗易懂，可以提供一些问题的查阅。考虑到作为理论基础性课程教学所确定的内容的稳定性和相应课程关于人才培养的实际需要，本次修订没有追求对知识点及其讲述顺序的调整，主要是进一步提高其可读性、系统性、严密性，特别对一些不太容易掌握含义的地方做了更清楚、更确切的描述，进一步提高了可理解性。

我们必须承认，本课程的基本内容高度抽象，虽然在写作中按照理工科人才培养的实际需要，强调了构造、等价变化等设计形态的内容，但是与其他的课程相比，也难免有一些难度。如何更好地解决这些问题，我们渴望读者能够给出宝贵的建议。另外，书中难免有这样或那样的错误，也恳请读者不吝赐教。联系地址： jiangzl@bjut.edu.cn。作者[]2007年4月第1版FOREWORD计算机科学与技术学科要求学生具有形式化描述和抽象思维能力，并且能够很好地掌握逻辑思维方法。我们称其为“计算思维”能力，或者叫做“计算机思维”能力。当然，一种能力的培养决不是一、两门孤立的课程可以实现的，尤其是思维能力的培养更是如此。它需要一系列课程，并且通过长期的学习和实践来完成。

形式语言与自动机理论不仅对问题及其求解提供了良好的形式化描述工具，更在通过适当的描述和解析而降低难度之后，成为对本科生和研究生进行“计算思维”能力培养的一门重要技术基础课程。

抽象和形式化是本书所涉及内容的主要特点。在这里，既有严格的理论证明，又具有很强的构造性。包含一些基本模型、模型的建立、性质等。通过对本课程的学习，除了使学生掌握正则语言、下文无关语言的文法、识别模型及其基本性质、图灵机的基本知识以外，主要致力于培养学生的形式化描述和抽象思维能力。同时使学生了解和初步掌握“问题、形式化描述、自动化（计算机化）”的解题思路。这样，我们就扣上了“什么能被有效地自动化”这一计算学科的主题。

当我们用计算机进行问题的求解时，需要实现对“问题”所在系统的状态及其变换的描述，要用适当的数据在计算机中表示该问题，并用适当的算法通过对这些数据的变换来获得问题的求解结果。因此，对问题进行抽象和形式化表示，然后进行处理，是进行计算机问题求解的基本途径。形式语言与自动机理论给出了一类基本问题的基本描述与计算模型——抽象表示。并通过研究这些模型的性质及其变化方法来对这些问题进行研究。它们都是问题的数学模型化的典范，给计算机问题求解提供了一种优美而坚实的基础，而且，它也向人们展示了一种典型的方法和思想。另外，形式语言与自动机理论还是研究算法及其理论的基础。

形式语言与自动机理论对于一个计算机科学与技术工作者来说，是非常重要的。它已经成为国际上计算机科学与技术专业本科生的一门重要课程。ACM和IEEE CC2001及《中国计算机科学与技术学科教程2002》（简称为CCC2002）给出了明确的要求。这里面不仅含有本学科最基本的知识内容，更涉及本学科方法论中所包含的全部3个学科形态。它可以被用来引导学生站在更高的高度去看待问题，去粗存真，直击本质，抓住问题及求解的关键点，以“计算机”的方式解决问题。

《形式语言与自动机理论》一书包括了CC2001和CCC2002规定的全部相关知识单元的内容，并且完全满足CC2001 建议的高级课程——自动机理论的教学大纲的要求。它不仅是后续课《编译原理》的理论基础，而且还广泛地用于一些新兴的研究领域。与国外现有的教材比较，《形式语言与自动机理论》一书主要突出了3个特点： ①充分考虑国内教学计划的容量，进行内容的取舍和组织； ②在培养读者的计算思维能力上做出进一步的尝试； ③主要考虑国内读者的特点，并且按照国内的教学风格的要求讨论问题。本书将按照小节清晰地列举出相关知识点，给出主要内容的解读。通过这些，进一步地讨论讲解学习的要点、问题分析、求解思路和方法、注意事项等内容，为读者学习和掌握原书中的知识点和问题求解方法、体会问题求解的核心思想提供帮助。考虑到初学者在解答习题中将会遇到的主要困难，本书选择了一些典型习题，并且给出了解答及分析。

形式语言与自动机理论课程的教学，最大的问题有两个，一是内容非常抽象，这就导致阅读起来比较枯燥，而且它的作用主要是在潜移默化中体现的，难以让学生看出其“用处”，似乎让人感到学习这门课程是在“自讨辛苦”，而且这种“辛苦”没有太大的意义，不如学习Java语言等编程更容易，更实用;其二是这些内容具有较大的难度，难以找到体验感性认识的具体实例，这就导致读者难以发现相关知识点的来龙去脉，以达到深入领会之目的。要想解决这两个问题，必须掌握问题求解的思想和方法，并且通过对它们的研究，来领略这门课程在高度抽象和形式化下的优美和乐趣，使这些看似抽象枯燥的内容活起来。实际上，许多内容都可能是读者自己的体会，哪怕这些体会是不完善的，甚至是过于理想化（理性）的，与历史不十分符合的。但是，它们一定是更理性的“思路”和“想法”。实际上，这正是人们在科学研究中所努力追求的。

虽然目前在国内的计算机科学与技术学科的本科生的课程教学计划中，设置形式语言与自动机理论课程的学校还不是很普遍，甚至在一些学校的研究生的培养方案中也还未开设此课程，但是，随着我国的计算机科学与技术学科教学的不断发展和条件的逐渐成熟，将会有越来越多的学校开设本课程。

本书共分12章。为了便于阅读，从第1章到第10章完全与原书结构相对应。第1章回顾在离散数学中学过的本书将要用到的一些基础知识，为后续的章节做好准备。由于主要是为了复习，所以这里给出的是知识点和应该注意的事项。除最后一节的“形式语言及其相关的基本概念”为新内容外，其他内容都可以由学生自学。第2章到第8章是教学的重点内容，主要讨论正则语言和上下文无关语言的文法、自动机描述及其性质。第9章对计算进行介绍，包括一般计算模型图灵机的概念、构造方法、修改，与计算相关的不可判定性、P\|NP等问题。第10章介绍上下文有关语言。在这些章节中，以知识点、主要内容解读、典型习题解析的形式，对讨论的内容进行归纳和解析。第11章对本书的内容按类进行全面总结。在第12章中安排了教学设计，从总体上讨论本课程的讲授等问题。

由于作者水平有限，书中的错误和不当之处在所难免，敬请读者批评指正。

作者2003年6月

第1章绪论11.1集合的基础知识2

1.1.1集合及其表示2

1.1.2集合之间的关系3

1.1.3集合的运算4

1.2关系5

1.2.1二元关系5

1.2.2递归定义与归纳证明6

1.2.3关系的闭包6

1.3图7

1.3.1无向图7

1.3.2有向图8

1.3.3树8

1.4语言9

1.4.1什么是语言9

1.4.2形式语言与自动机理论的产生与作用10

1.4.3基本概念11

1.5小结14

1.6典型习题解析14

第2章文法20

2.1启示21

2.2形式定义22

2.3文法的构造26

2.4文法的乔姆斯基体系29

2.5空语句32

2.6小结33

2.7典型习题解析33[][]形式语言与自动机理论教学参考书(第3版)[]第3章有穷状态自动机45

3.1语言的识别46

3.2有穷状态自动机46

3.3不确定的有穷状态自动机51

3.3.1作为对DFA的修改51

3.3.2NFA的形式定义51

3.3.3NFA与DFA等价52

3.4带空移动的有穷状态自动机55

3.5FA是正则语言的识别器57

3.5.1FA与右线性文法57

3.5.2FA与左线性文法58

3.6FA的一些变形60

3.6.1双向有穷状态自动机60

3.6.2带输出的FA61

3.7小结62

3.8典型习题解析63

第4章正则表达式70

4.1启示70

4.2正则表达式的形式定义71

4.3正则表达式与FA等价73

4.3.1正则表达式到FA的等价变换73

4.3.2正则语言可以用正则表达式表示75

4.4正则语言等价模型的总结77

4.5小结78

4.6典型习题解析79

第5章正则语言的性质83

5.1正则语言的泵引理84

5.2正则语言的封闭性85

5.3MyhillNerode定理与DFA的极小化89

5.3.1MyhillNerode定理89

5.3.2DFA的极小化93

5.4关于正则语言的判定算法95

5.5小结96

5.6典型习题解析96

第6章上下文无关语言103

6.1上下文无关文法104

6.1.1上下文无关文法的派生树104

6.1.2二义性107

6.1.3自顶向下的分析和自底向上的分析109

6.2上下文无关文法的化简110

6.2.1去无用符号110

6.2.2去ε产生式113

6.2.3去单一产生式116

6.3乔姆斯基范式117

6.4格雷巴赫范式119

6.5自嵌套文法122

6.6小结123

6.7典型习题解析123

第7章下推自动机127

7.1基本定义128

7.2PDA与CFG等价130

7.2.1PDA用空栈接受和用终止状态接受等价130

7.2.2PDA与CFG等价131

7.3小结133

7.4典型习题解析134

第8章上下文无关语言的性质140

8.1上下文无关语言的泵引理141

8.2上下文无关语言的封闭性144

8.3上下文无关语言的判定算法146

8.3.1L空否的判定147

8.3.2L是否有穷的判定147

8.3.3x是否为L的句子的判定148

8.4小结150

8.5典型习题解析150

第9章图灵机152

9.1基本概念153

9.1.1基本图灵机153

9.1.2图灵机作为非负整函数的计算模型157

9.1.3图灵机的构造157

9.2图灵机的变形160

9.2.1双向无穷带图灵机160

9.2.2多带图灵机163

9.2.3不确定的图灵机164

9.2.4多维图灵机165

9.2.5其他图灵机166

9.3通用图灵机168

9.4几个相关的概念170

9.4.1可计算性170

9.4.2P与NP相关问题170

9.5小结171

9.6典型习题解析171

第10章上下文有关语言183

10.1图灵机与短语结构文法的等价性183

10.2线性有界自动机及其与上下文有关文法的等价性186

10.3小结187

10.4典型习题解析187

第11章内容归纳190

11.1文法与语言190

11.2正则语言190

11.3上下文无关语言191

11.4图灵机192

第12章教学设计194

12.1概述194

12.2课程内容体系195

12.2.1课程的基本描述195

12.2.2教学定位195

12.2.3知识点与学时分配196

12.3讲授提示198

12.3.1重点与难点198

12.3.2讲授中应注意的方法等问题201

12.4习题与实验202

12.4.1指导思想202

12.4.2关于大作业和实验202

12.5考试与成绩记载202

12.5.1成绩评定202

12.5.2考题设计203

参考文献204