改革视点

形式语言与自动机理论是计算机科学与技术领域的三大基础理论之一。它被广泛应用于机器语言、编译原理、自动控制、图像处理当中，是程序设计语言编译器最重要的也是必不可少的理论支撑。近年来，随着人工智能的快速发展，有限自动机理论当中的“图灵机、图灵测试”历久弥新，焕发出了新的生命力。

计算机科学与工程学院陈文宇教授牵头，周益民教授、余盛季副教授共同讲授的《有限自动机理论》是夯实研究生学术功底，构筑坚实理论基础的重要课程。要学好这门课程并不容易，一方面教学内容高度抽象，难以快速直接地找到具象场景；另一方面课程知识容量多、难度大，为学生深刻理解理论内在机理带来了不小的挑战。

在课程组教师们的不懈努力下，这门课程逐渐变得有趣起来。在教学活动中，课程组摒弃了繁琐的定理证明过程，引导学生思考解决问题的方法、拓展学生解决问题的思路，实实在在地提升了学生的创新思维能力。

陈文宇教授为学生授课

夯实理论基础，增强创新后劲

“研究生的适应能力以及创新能力在很大程度上取决于坚实的理论基础和专业基础知识，这是高质量研究生教育的重要特征之一。”陈文宇教授指出，“在计算机科学技术突飞猛进、专业知识日新月异的时代，只有扎实掌握专业的计算机理论基础，才能打好进行创造性研究的基础”。

课程组认为，计算机科学与技术学科强调计算思维能力、算法设计与分析能力、程序设计与实现能力，进一步强调对计算机系统的认知、分析、设计和运用能力。这些都是计算机学科区别于其他学科的重要特征。理论基础知识是计算机科学与技术的真正灵魂。

本科阶段，计算机专业学生以观察、描述、比较、分类、推断、应用、创造等科学思维过程为主，强调自学能力的再培养。到了研究生阶段，需要进一步加强逻辑思维训练、增强创新实践能力。这也就意味着，研究生需要更加宽厚坚实的理论基础。计算理论是研究使用计算机解决计算问题的数学理论，而自动机理论正是其三大核心领域之一，是学习计算理论的良好起点。

有限自动机理论不仅能提高学生的感知能力，也能提高思维的敏捷性，使学生考虑问题仔细、严谨、周密、有理有据；可以由具体形象思维逐渐向抽象思维过渡，从而促进逻辑思维和创造力的发展；可以使逻辑思维过程清晰化、条理化、整体化，从而提高推理、判断、分析问题和解决问题的能力。为此，课程组十分注重引导学生深刻认识夯实理论的重要意义，鼓励学生不仅要知其然，更要知其所以然，同时鼓励学生拿出迎难而上的勇气！

陈文宇教授在课堂上推导证明

启发心灵智慧，阐释迷人思想

怎么让学生知其所以然呢？课程组的答案是：“思想！”

“我们要努力让学生感受到，计算理论并不神秘，也不令人厌烦，而是容易理解的，甚至是有趣的。”陈文宇教授告诉学生，“计算理论中包含许多迷人而重要的思想，要体会、感悟思想的闪光，并且体会大师们当初发现这些思想而获得的极大的乐趣”。

诚然，丰富的课程内容中会有许多琐碎的细节，但课程组提醒同学们，要抓住思想，而不要陷入细节的单调乏味当中。同学们在学习过程中，既可以汲取计算机源头理论当时提出、发展、演进的知识体系，又可以结合现代人工智能发展，从古典理论中唤起好奇、启发思维。

“形式语言”是该课程的第二章。生动讲述形式语言与自动机的发展历程，是帮助研究生理解其背后思想的重要途径和典型案例。语言学家乔姆斯基（Chomsky）是最早从产生语言的角度研究语言的著名学者，并提出了具有革命意义的“转换生成语法”。他的贡献在形式语言理论发展中具有至关重要的作用。

几乎是在同一时期，数学家克林（Kleene）从识别语言的角度来研究语言，给出了语言的另一种描述方式。他建立了自动机模型来识别（接收）一个语言：按照某种识别规则构造自动机，该自动机就定义了一个语言，该语言由自动机能够识别的所有字符串构成。

语言的两种不同的定义方式进一步引起了人们的研究兴趣。1959年，乔姆斯基将他本人的形式语言的研究成果和克林的自动机研究成果结合起来，不仅确定了文法和自动机分别从产生和识别角度定义语言，而且证明了文法与自动机的等价性。形式语言与自动机理论才真正诞生，并被置于数学的光芒之下。

如此这般，从“思想史”的角度向学生展示“思想”的嬗变脉络，既让学生直击课程的核心和精髓，又以故事化的方式激发了学生的兴趣，取得了良好的课堂教学效果，赢得了学生的点赞。

学生在课堂上认真听讲

遵循教学规律，循序渐进学习

《有限自动机理论》课程共有六章，分别是基础知识、形式语言、有限状态自动机、正则语言、下推自动机、图灵机。内容有难度，但课程组自有妙招引导学生渐入佳境。

在第一章基础知识中，课程组系统、扼要地介绍有限自动机理论中所需的数学基础知识，包括集合及其运算、关系、证明的方法、图与树的概念，以及语言、常用术语、形式语言与自动机的发展概况等，既是复习基础知识，也初步介绍了形式语言的概念。随后的各章节逐步深入，由易到难，引导学生拾级而上、节节攀升。在涉及难点内容时，老师会通过多种方法帮助学生深刻理解。

课堂上讲解重点难点内容“图灵机”

有限状态自动机、下推自动机、图灵机是课程的三大重点，也是难点所在。尤其是自动机与文法之间的对应等价关系理论，常令学生绞尽脑汁。这是因为，学生一般对于构造自动机比较感兴趣，因为它可以唤起学生的工程实践兴趣。但是，证明自动机与文法之间的等价关系是从理论到理论的推导，需要构建抽象的思维，而且是离散的抽象过程。在这里，课程组讲得细致深入，并给学生留下消化吸收的时间。

有限状态自动机最主要的表现形式是状态转换图。在讲解这部分内容时，课程组利用今天的计算机绘图语言dot，并结合Graphviz绘图环境，引导学生通过程序设计的办法让计算机轻松绘制表现力强的状态转换图。这一过程既训练了学生对正则表达式的读取、理解，又利用自动机的构造方法进行了形式化描述，最后通过程序设计达到自动出图的效果，形成了教与学的闭环。

利用栈进行简单左右括号匹配的算法是学生已经掌握的算法技能，到了研究生阶段，通过进一步学习，学生开始了解采用下推自动机进行括号匹配的字符串检测也是不错的便利方式。老师在教学中引导学生进一步考虑括号的嵌套层数，建立对“广义表”表达深度的等价关系，引申出下推自动机栈的最大使用深度对应的深度信息。这是一个循序渐进的过程，课程组通过“元认知”推广到一般情形的教学方法，使学生的接受度大大提高。

在教学方法上，课程组还把线上线下学习结合起来，学生可以在线上预先学习基本知识，了解专业术语，思考自动机的一般理论和方法。线下课堂教学重在阐述难点和要点，特别是对各自动机的构造过程、相关的算法思想进行深入解析，重在课堂交互和深入研讨，引导学生思考，保持课堂教学的流畅度。老师还通过对学习过程的设计，督促学生对基本知识点透彻掌握，引导学生不要把注意放在奇、难、怪的题目上。

周益民教授在课堂授课

“我们的目标是培养学生掌握文法、产生语言，利用三大自动机接收语言，进一步利用自动机进行原始基础的1-进制、2-进制四则运算。”周益民教授说，“我期望这门课程不仅让学生掌握三大自动机的构造，更要引导学生用心体会几十年来计算机学人定义和发明各类自动机的心路历程，为研究生树立科技创新的勇气和路径参考！”

2018级研究生张旭表示，“在研究生一年级期间，怀揣着对人工智能理论和形式语言的热情学习了这门课程。老师讲课很幽默，能把比较困难的问题通俗地解释给同学们。”2019级研究生余红表示，“老师上课讲解知识点详细透彻，对难以理解的地方会深入分析，努力让学生学懂弄通。” 

余盛季副教授与学生互动

浸润学生心灵，为国铸魂育人

“讲课首先要有趣，并激发学生的兴趣！”余盛季副教授表示，课程组一直在努力引导学生掌握问题求解的思想和方法，领略理论在高度抽象和形式化下的优美和乐趣，使这些枯燥的内容鲜活起来，使学生自己能够创造“思路”和“想法”。

为此，课程组逐步将科学思维过程融入学生的知识结构之中，引导学生通过比较、观察，把新法则纳入到原有法则系统中，构成紧密联系和融汇贯通的知识网络；在课堂互动中，善于针对学生情况，提出启发性的问题，让学生主动思考、理解、掌握问题要点，并培养学生分析问题和解决问题的能力。

课程组很重视“课程思政”建设，引导学生塑造正确的世界观、人生观、价值观。而越接近专业性的思政教育，越能打动学生的内心。

在回顾有限自动机的发展历程时，课程组不仅讲图灵、乔姆斯基、巴赫等为机器识别语言及早期人工智能的发展作出过突出贡献的科学大家，引导学生感受他们的创新思维和科学精神，也着重讲述姚期智院士等最近20年作出重要学术贡献的华人科学家的故事，增强同学们追求卓越、攀登高峰的信心。

提出“Dolev-Yao模型”的姚期智院士，用形式化模型讨论分析密码协议的安全性，并首次证明了“量子图灵机模型”与“量子电路模型”的等价性，为图灵机的现实应用找到了理论依据。

“可以预见，未来在科学领域将有更多的中国科学家走在时代前列。”课程组老师鼓励同学们，要从姚期智院士等科学家的奋斗历程中汲取力量，勇敢迎接挑战，砥砺奋进、勇毅前行。