第4版前言FOREWORD



本书自第1版出版以来，一直受到读者的厚爱，甚至被认为是国内“形式语言与自动机理论”课程最合适的教材，第2版和第3版先后入选普通高等教育“十一五”国家级规划教材和“十二五”普通高等教育本科国家级规划教材，第2版在2008年还被教育部评为国家级普通高等教育精品教材。尽管该教材是基础理论课程教材，按照需要，2013年出版的第3版也到了修订的时候。另外，自2013年以来，作者在教学中也有了一些新的体会，加上我国高等教育正在跨入新的阶段，所以，在第4版出版前，还是有一些话想和大家交流。
首先，到2020年，我国全面建成了小康社会，目前中国共产党正在领导我们迈向第二个百年目标，把中国建成一个富强、民主、文明、和谐的社会主义现代化国家。这个新的发展时期的人才需求明显高了，这给高等教育提出了新的要求。我们必须为党和国家培养更多水平更高、质量更好、对未来高速度发展适应性更强、德智体美劳全面发展的社会主义建设者和接班人。他们需要有更强的创新能力、更强的可持续发展能力，要能更好地承担并高质量、高水平地完成发展之潮头的引领性工作。
其次，近些年来，随着人才培养标准的建立和质量意识的强化，我们进一步清晰地表达了本科教育的定位和要求，特别是将工科人才培养的基本定位具体准确地描述为解决复杂工程问题。而教育意义上的复杂工程问题的最基本特征是“能够运用深入的工程原理经过分析才有可能解决”。另一个重要特征是“需要通过建立抽象模型才能解决，而且在建模过程中体现出创造性”。这些使得我们对工科本科教育致力于未来工程师的培养所需的教学内容和基本追求有了更深刻的体会。不仅进一步明确了本科教育不能是产品教育，不能导致学生毕业后在谈到自己学了什么、有什么能力的时候，首先想到的是学了哪几种高级程序设计语言，这个说“我是学Java语言的”，那个说“我是学Python语言的”，或者说我学了3种或4种“编程”语言，而是要夯实学生的可持续发展基础，能够创造性地综合运用数学、自然科学、计算机、工程基础和专业知识分析和解决问题。使得学生未来不会仅仅凭借记忆的知识去解决问题，去和机器抢饭碗。“形式语言与自动机理论”课程在这些方面有着天然的优势。要发挥这一优势，课程教学需要进一步在以下方面发力。
第一，努力为学生“能够运用深入的工程原理，经过分析解决问题”奠定坚实的基础。一是课程内容的选择和组织，要保证能够使学生学到“深入的工程原理”，不仅教师要“讲到”，重要的是学生要“学到”。所以，既不能“因难就删”，也不是“越难、越多就越好”，要使学生使劲“跳一跳”，而且“跳一跳”后能够得到。二是要强调“分析”。不能只是简单地告诉学生有什么、是什么，而是要带着学生探讨出什么，更不能念PPT、照本宣科。三是追求恰当的“运用”。就本课程而言，就是要首先保证适当、有效的习题。因为“习题”可以在课内最高效地获得对“知识”的适当运用。当然，如果学时比较充裕，安排学生依据一些基本结论，设计实现出相应的自动计算系统，也是非常有意义的。
一个重要的问题是，要破除学生认为这些抽象理论不是“编程”所以没有用的错误认识。
第二，要按照学生的培养需求强调恰当学科形态的内容。一定要将本课程的教学置于整个人才培养体系中，不能就课程说课程，更不能从定义到定理，将课程上得干巴巴的。就目前我国计算机类专业本科教育而言，虽然有4200多个专业点，但基本上都是面向工程和应用型人才培养的。所以，一般来说，强调“设计形态”的内容是本课程的基本取向。虽然本课程的数学特征非常明显，在统计中应该像集合与图论、近世代数、数理逻辑、组合数学一样，将其归入数学类课程，但对工科学生来说，不能简单地从定义到定理，不能简单地追求结论的常规证明。所以，需要重视模型的构造、等价变换，以及基于模型实现的构造性证明，引导学生学习如何基于模型实现问题的系统求解，并能够证明解的正确性，从而对工程的完备实现提供保证。
第4版前言形式语言与自动机理论教学参考书（第4版）第三，一定要坚持理论指导下的实践。本科教育的实践，不是简单地动手，而是动脑为前提的动手。对本科教育而言，很多时候“动手能力差”实际是“动脑能力差”。有人错误地将考试分数比较高但设计开发能力较差的学生说成是“理论学得好”“动手能力差”的学生。分数高，不一定是理论学得好。实际上，既然这类学生“动手能力差”，那么他们肯定并没有真正学懂这些理论，因为理论是源于实践又反过来指导新的实践的。他们之所以获得了“高分”，是评价体系出了问题，很可能是针对基本知识的集合简单理解进行的评价。
第四，本课程的“动手”鼓励学生认真求解适当、适量的习题，一般不安排到实验室做实验。而且在有效的习题求解“练习”中也不能是简单地“照猫画虎”，而是要综合地、创造性地解决问题。要注意体现基于基本原理的探索。所以，即使是习题课，也不能简单地告诉学生如何解题。要通过这类实践练习，使学生深入理解课程内容，亲口尝尝这个“梨子”的滋味。另外，要注意习题的难易搭配。防止全是比较简单的题导致无法达到训练的目的。还要防止给学生太多做不出来的题，这样会导致学生失去信心、失去兴趣。再者，在习题中，构造性题目的占比应该大一些。本书各章给出的习题总体上是按照这个想法设置的，教师还需要根据学生的具体情况，从中做出适当的选择。
第五，引导学生基于基本原理通过分析去求解问题，而不是简单地追求解题技巧，更不是简单地追求“套用”“模仿”。这有利于学生科学意识的培养，使得他们能够在高层次上解决问题。
授课的过程中，要引导和鼓励学生读书，特别是读经典图书。我们都知道“书中自有黄金屋，书中自有颜如玉”，书中，尤其是经典图书中确实有，但是要把这些“黄金屋”“颜如玉”变成学生的，唯有静下心来认真、深入读书。所以，教师不仅要努力为自己构建一个安静的书桌，也要为处于重要的打基础阶段的学生有一张安静的书桌而构建一个良好的生态环境。
第六，强化学生思维能力的培养。前面已经强调了课程要努力引导学生分析问题，教师要在对问题的研究中教，学生要在对未知的探讨中学，形成心灵的高层次互动，努力将课程上成思维体操课。只有让学生学会独立思考，他们才会逐渐形成解决复杂工程问题的能力和可持续发展的能力。
本书除了保持内容的严格叙述外，也试着探索对一些关键思路的描述，引导读者发现问题、分析问题、解决问题，以期对以上几点给出一些回应。当然，这些本身都是探索性的，一定有不妥当之处，还请读者毫无保留地指出来，并且希望教师也能结合自己的教学去探索，以便编写出更好、更适应新时期教学要求的教材，当然不仅仅是“形式语言与自动机理论”课程的教材。希望通过大家的共同努力，使本书及其对应的课程能够在高水平科技人才，尤其是高水平计算机类专业人才的培养中发挥更多作用。
对书中的错误和有关建议，请读者不吝赐教。联系方式： jiangzl@bjut.edu.cn。

作者
2023年1月第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月形式语言与自动机理论教学参考书（第4版）第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月