形式语言与自动机理论是计算机科学与技术专业的一门重要课程。本书是作者结合其近30年来在大学讲授该门课程的经验和体会，选择和组织有关内容撰写而成。基于计算机问题求解的需要讨论正则语言、上下文无关语言的文法、识别模型及其性质、图灵机的基本知识。其内容特点是抽象和形式化，既有严格的理论证明，又具有很强的构造性。叙述中特别注意引导读者分析与解决问题，以培养学生的形式化描述和抽象思维能力，使学生了解和初步掌握“问题、形式化、自动化（计算机化）”的解题思路。为了便于学生对内容的掌握，附录A还给出了建议的教学设计。

本书配套出版有《形式语言与自动机理论教学参考书（第3版）》，归纳各章知识点，解读主要内容，解析典型习题。

本书适合作为计算机学科研究生和高年级本科生的教材，也可供相关专业的学生、教师和科研人员参考。

第3版FOREWORD

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

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

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

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

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

对书中的错误，请读者不吝赐教。联系地址：jiangzl@bjut.edu.cn。

作者2013年2月

形式语言与自动机理论(第3版)第2版

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

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

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

我们必须承认，本课程的基本内容高度抽象，虽然在写作中按照理工科人才培养的实际需要，强调了构造、等价变化等设计形态的内容，但是与其他的课程相比，也难免有一些难度。如何更好地解决这些问题，我们渴望读者能够给出宝贵的建议。另外，书中难免有这样或那样的错误，也恳请读者不吝赐教。联系地址： jiangzl@bjut.edu.cn。作者2007年4月第1版FOREWORD当我们用计算机进行问题的求解时，首先需要建立模型并用适当的数据进行问题表示，然后再用适当的算法通过对这些数据进行变换来获得问题的求解结果。因此，对问题进行抽象和形式化表示，然后进行处理是进行计算机问题求解的基本途径。形式语言与自动机理论给出了一类基本问题的基本描述与计算模型——抽象表示，并通过研究这些模型的性质及其变化方法来对这些问题进行研究。这些模型都是问题模型化的典范，给计算机问题求解提供了一种优美而坚实的基础，而且，也向人们展示了一种典型的方法和思想。另外，它还是研究算法及其理论的基础。

形式语言与自动机理论对计算机科学与技术工作者是非常重要的，它已经成为国际上计算机科学与技术专业本科生的一门重要课程。CC2001CS和CCC2002给出了明确的要求，里面不仅含有本学科最基本的知识内容，更涉及本学科方法论中所包含的三个学科形态。它们可以被用来引导学生站在更高的高度去看待问题，去粗存真，直击本质，从关键点上以“计算机”的方式解决问题。难怪作者在1989年到美国进修时被首先问到的两个问题之一就是“是否学过形式语言与自动机理论？”（另一个问题是“是否学习过算法设计与分析？”）。据统计，在每年GRE的考题中，大约有8~15道题是关于本课程内容的。

本书包括了CC2001CS和CCC2002规定的全部相关知识单元的内容，并且完全满足CC2001 建议的高级课程自动机理论的教学大纲的要求。它不仅是后续课“编译原理”的理论基础，而且还广泛地用于一些新兴的研究领域。与国外现有的教材比较，本书主要突出如下特点： ①充分考虑国内教学计划的容量，进行内容的取舍和组织； ②在培养读者的计算思维能力上做进一步的尝试； ③尽量照顾国内读者的特点，并且按照国内的教学风格讨论问题。

计算机科学与技术学科要求学生具有形式化描述和抽象思维能力，掌握逻辑思维方法。我们称这种能力为“计算思维”能力，或者叫“计算机思维”能力。当然，一种能力的培养决不是一两门孤立的课程可以实现的，尤其是思维能力的培养，更是如此。它需要一系列的课程，并且通过长期的修养来完成。本课程是这个系列课程中的一门，关于这个系列课程的具体讨论我们将放到1.4节进行。本书内容的主要特点是抽象和形式化，既有严格的理论证明，又具有很强的构造性，包含一些基本模型、模型的建立与性质等。通过对本课程的学习，除了使学生掌握有关正则语言、上下文无关语言的文法、识别模型及其基本性质、图灵机的基本知识外，更重要的是还能培养学生的形式化描述和抽象思维能力，同时使学生了解和初步掌握“问题、形式化描述、自动化（计算机化）”的解题思路。这样，我们就扣上“什么能被有效地自动化”这一计算学科的主题。

哈尔滨工业大学从1977级本科生开始，一直坚持在本科教学计划中设置此课程。为了给没有学过此课程的研究生提供机会，还从1982级工学硕士研究生开始，在其计算机科学与技术学科的硕士研究生的培养方案中安排了此门课程。与其他课程相配合，在对学生进行计算思维能力的培养上，取得了良好的效果。本书是作者根据其在该校进行10余年的形式语言与自动机理论课程教学的教案，并参考有关教材撰写而成的。促使作者将教案变成教材的另一个原因是，在国内的教材市场上，这类教材少之又少，根本无法与它在计算机学科的人才培养中的地位相匹配。另外，我们也希望将自己积累的经验和体会提供给大家参考。在本书中，我们希望通过对一些思想和方法的介绍，使读者在这门课程中享受其高度抽象和形式化所带来的美和乐趣。希望通过这些努力，能使这些看似抽象枯燥的内容活起来。许多都是我们自己的体会，其中也难免存在不完善的地方。为了帮助读者更好地学习，附录A提供了包括内容取舍、讲授要点等在内的教学设计。在每章的后面，我们都附有一定量的习题。这些习题用来深化对课程知识的理解，并为读者提供应用所学知识解决问题的机会，使读者亲身体验用相关方法和思想进行探索的乐趣。特别难的习题我们没有列出来，请感兴趣的读者查阅本书后面给出的参考文献。

第1版形式语言与自动机理论(第3版)

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

本书共分10章。第1章绪论，带领读者回顾在离散数学中学过的本书将要用到的一些基础知识，包括集合及其表示，集合之间的关系，集合的运算，无穷集合，二元关系及其性质，等价关系与等价类，关系的合成，关系的闭包，无向图，有向图，树；另外，介绍形式语言及其相关的基本概念，为后续的章节做准备。第2章介绍文法，包括文法的直观意义与形式定义，推导，归约，文法产生的语言、句子、句型，文法的构造，乔姆斯基体系，左线性文法，右线性文法，空语句。第3章讨论有穷状态自动机，包括DFA作为对实际问题的抽象，直观物理模型，形式定义，DFA接受的句子、语言，状态转移图，构造方法，NFA与DFA的等价性，带空移动的NFA与NFA的等价性，正则文法与FA的等价性及其相互转换方法，基本问题的判定。第4章研究正则表达式，包括正则表达式的定义及其与FA的等价性证明。第5章讨论正则语言的性质，包括正则语言的泵引理的证明及其应用，正则语言的封闭性， MyhillNerode定理与FA的极小化，判定算法。第6章讲述上下文无关语言，包括文法二义性，派生与派生树，上下文无关文法的化简，乔姆斯基范式，格雷巴赫范式。第7章叙述下推自动机，包括下推自动机的基本定义，下推自动机用终态接受的语言和用空栈接受的语言，构造方法，下推自动机与上下文无关文法的等价性。第8章研究上下文无关语言的性质，包括上下文无关语言的泵引理、Ogden引理及其应用，上下文无关语言的封闭性，判定算法。第9章介绍图灵机，包括图灵机作为一个计算模型的基本定义，图灵机接受的语言，构造技术，通用图灵机，丘奇图灵论题，图灵机的变形，可计算语言，不可判定性，PNP问题。第10章介绍上下文有关语言，包括图灵机与短语结构文法的等价性，线性有界自动机的定义及其与上下文有关语言的关系。

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

作者2002年12月

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

1.1.1集合及其表示2

1.1.2集合之间的关系4

1.1.3集合的运算5

1.2关系10

1.2.1二元关系10

1.2.2等价关系与等价类11

1.2.3关系的合成12

1.2.4递归定义与归纳证明12

1.2.5关系的闭包15

1.3图15

1.3.1无向图16

1.3.2有向图17

1.3.3树19

1.4语言20

1.4.1什么是语言20

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

1.4.3基本概念23

1.5小结28

习题29

第2章文法35

2.1启示36

2.2形式定义38

2.3文法的构造46

2.4文法的乔姆斯基体系54

2.5空语句64

2.6小结66

习题66形式语言与自动机理论(第3版)第3章有穷状态自动机70

3.1语言的识别70

3.2有穷状态自动机72

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

3.3.1作为对DFA的修改83

3.3.2NFA的形式定义84

3.3.3NFA与DFA等价86

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

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

3.5.1FA与右线性文法94

3.5.2FA与左线性文法98

3.6FA的一些变形99

3.6.1双向有穷状态自动机100

3.6.2带输出的FA101

3.7小结102

习题103

第4章正则表达式108

4.1启示108

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

4.3正则表达式与FA等价111

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

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

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

4.5小结126

习题126

第5章正则语言的性质129

5.1正则语言的泵引理129

5.2正则语言的封闭性134

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

5.3.1MyhillNerode 定理140

5.3.2DFA的极小化148

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

5.5小结157

习题158

第6章上下文无关语言160

6.1上下文无关文法160

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

6.1.2二义性166

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

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

6.2.1去无用符号172

6.2.2去ε产生式175

6.2.3去单一产生式组178

6.3乔姆斯基范式181

6.4格雷巴赫范式184

6.5自嵌套文法189

6.6小结190

习题190

第7章下推自动机194

7.1基本定义194

7.2PDA与CFG等价200

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

7.2.2PDA与CFG等价203

7.3小结212

习题212

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

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

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

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

8.3.1L空否的判定226

8.3.2L是否有穷的判定227

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

8.4小结230

习题230

第9章图灵机231

9.1基本概念232

9.1.1基本图灵机232

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

9.1.3图灵机的构造241

9.2图灵机的变形247

9.2.1双向无穷带图灵机247

9.2.2多带图灵机250

9.2.3不确定的图灵机252

9.2.4多维图灵机253

9.2.5其他图灵机255

9.3通用图灵机257

9.4几个相关的概念259

9.4.1可计算性259

9.4.2P与NP相关问题259

9.5小结260

习题260

第10章上下文有关语言263

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

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

10.3小结267

习题267

附录A教学设计269

A.1课程内容体系269

A.1.1基本描述269

A.1.2教学定位269

A.1.3知识点与学时分配270

A.2课程的讲授271

A.2.1重点与难点271

A.2.2讲授中应注意的方法等问题275

A.3作业276

A.3.1指导思想276

A.3.2关于大作业和实验276

A.4考试与成绩记载276

A.4.1成绩评定276

A.4.2考题设计276

附录B缩写符号278词汇索引280

参考文献287