形式語言與自動機理論是計算機科學與技術(shù)領(lǐng)域的三大基礎(chǔ)理論之一。它被廣泛應(yīng)用于機器語言、編譯原理、自動控制、圖像處理當中，是程序設(shè)計語言編譯器最重要的也是必不可少的理論支撐。近年來，隨著人工智能的快速發(fā)展，有限自動機理論當中的“圖靈機、圖靈測試”歷久彌新，煥發(fā)出了新的生命力。
計算機科學與工程學院陳文宇教授牽頭，周益民教授、余盛季副教授共同講授的《有限自動機理論》是夯實研究生學術(shù)功底，構(gòu)筑堅實理論基礎(chǔ)的重要課程。要學好這門課程并不容易，一方面教學內(nèi)容高度抽象，難以快速直接地找到具象場景；另一方面課程知識容量多、難度大，為學生深刻理解理論內(nèi)在機理帶來了不小的挑戰(zhàn)。
在課程組教師們的不懈努力下，這門課程逐漸變得有趣起來。在教學活動中，課程組摒棄了繁瑣的定理證明過程，引導學生思考解決問題的方法、拓展學生解決問題的思路，實實在在地提升了學生的創(chuàng)新思維能力。
陳文宇教授為學生授課
夯實理論基礎(chǔ)，增強創(chuàng)新后勁
“研究生的適應(yīng)能力以及創(chuàng)新能力在很大程度上取決于堅實的理論基礎(chǔ)和專業(yè)基礎(chǔ)知識，這是高質(zhì)量研究生教育的重要特征之一。”陳文宇教授指出，“在計算機科學技術(shù)突飛猛進、專業(yè)知識日新月異的時代，只有扎實掌握專業(yè)的計算機理論基礎(chǔ)，才能打好進行創(chuàng)造性研究的基礎(chǔ)”。
課程組認為，計算機科學與技術(shù)學科強調(diào)計算思維能力、算法設(shè)計與分析能力、程序設(shè)計與實現(xiàn)能力，進一步強調(diào)對計算機系統(tǒng)的認知、分析、設(shè)計和運用能力。這些都是計算機學科區(qū)別于其他學科的重要特征。理論基礎(chǔ)知識是計算機科學與技術(shù)的真正靈魂。
本科階段，計算機專業(yè)學生以觀察、描述、比較、分類、推斷、應(yīng)用、創(chuàng)造等科學思維過程為主，強調(diào)自學能力的再培養(yǎng)。到了研究生階段，需要進一步加強邏輯思維訓練、增強創(chuàng)新實踐能力。這也就意味著，研究生需要更加寬厚堅實的理論基礎(chǔ)。計算理論是研究使用計算機解決計算問題的數(shù)學理論，而自動機理論正是其三大核心領(lǐng)域之一，是學習計算理論的良好起點。
有限自動機理論不僅能提高學生的感知能力，也能提高思維的敏捷性，使學生考慮問題仔細、嚴謹、周密、有理有據(jù)；可以由具體形象思維逐漸向抽象思維過渡，從而促進邏輯思維和創(chuàng)造力的發(fā)展；可以使邏輯思維過程清晰化、條理化、整體化，從而提高推理、判斷、分析問題和解決問題的能力。為此，課程組十分注重引導學生深刻認識夯實理論的重要意義，鼓勵學生不僅要知其然，更要知其所以然，同時鼓勵學生拿出迎難而上的勇氣！
啟發(fā)心靈智慧，闡釋迷人思想
怎么讓學生知其所以然呢？課程組的答案是：“思想！”
“我們要努力讓學生感受到，計算理論并不神秘，也不令人厭煩，而是容易理解的，甚至是有趣的?！标愇挠罱淌诟嬖V學生，“計算理論中包含許多迷人而重要的思想，要體會、感悟思想的閃光，并且體會大師們當初發(fā)現(xiàn)這些思想而獲得的極大的樂趣”。
誠然，豐富的課程內(nèi)容中會有許多瑣碎的細節(jié)，但課程組提醒同學們，要抓住思想，而不要陷入細節(jié)的單調(diào)乏味當中。同學們在學習過程中，既可以汲取計算機源頭理論當時提出、發(fā)展、演進的知識體系，又可以結(jié)合現(xiàn)代人工智能發(fā)展，從古典理論中喚起好奇、啟發(fā)思維。
“形式語言”是該課程的第二章。生動講述形式語言與自動機的發(fā)展歷程，是幫助研究生理解其背后思想的重要途徑和典型案例。語言學家喬姆斯基（Chomsky）是最早從產(chǎn)生語言的角度研究語言的著名學者，并提出了具有革命意義的“轉(zhuǎn)換生成語法”。他的貢獻在形式語言理論發(fā)展中具有至關(guān)重要的作用。
幾乎是在同一時期，數(shù)學家克林（Kleene）從識別語言的角度來研究語言，給出了語言的另一種描述方式。他建立了自動機模型來識別（接收）一個語言：按照某種識別規(guī)則構(gòu)造自動機，該自動機就定義了一個語言，該語言由自動機能夠識別的所有字符串構(gòu)成。
語言的兩種不同的定義方式進一步引起了人們的研究興趣。1959年，喬姆斯基將他本人的形式語言的研究成果和克林的自動機研究成果結(jié)合起來，不僅確定了文法和自動機分別從產(chǎn)生和識別角度定義語言，而且證明了文法與自動機的等價性。形式語言與自動機理論才真正誕生，并被置于數(shù)學的光芒之下。
如此這般，從“思想史”的角度向?qū)W生展示“思想”的嬗變脈絡(luò)，既讓學生直擊課程的核心和精髓，又以故事化的方式激發(fā)了學生的興趣，取得了良好的課堂教學效果，贏得了學生的點贊。
遵循教學規(guī)律，循序漸進學習
《有限自動機理論》課程共有六章，分別是基礎(chǔ)知識、形式語言、有限狀態(tài)自動機、正則語言、下推自動機、圖靈機。內(nèi)容有難度，但課程組自有妙招引導學生漸入佳境。
在第一章基礎(chǔ)知識中，課程組系統(tǒng)、扼要地介紹有限自動機理論中所需的數(shù)學基礎(chǔ)知識，包括集合及其運算、關(guān)系、證明的方法、圖與樹的概念，以及語言、常用術(shù)語、形式語言與自動機的發(fā)展概況等，既是復習基礎(chǔ)知識，也初步介紹了形式語言的概念。隨后的各章節(jié)逐步深入，由易到難，引導學生拾級而上、節(jié)節(jié)攀升。在涉及難點內(nèi)容時，老師會通過多種方法幫助學生深刻理解。
有限狀態(tài)自動機、下推自動機、圖靈機是課程的三大重點，也是難點所在。尤其是自動機與文法之間的對應(yīng)等價關(guān)系理論，常令學生絞盡腦汁。這是因為，學生一般對于構(gòu)造自動機比較感興趣，因為它可以喚起學生的工程實踐興趣。但是，證明自動機與文法之間的等價關(guān)系是從理論到理論的推導，需要構(gòu)建抽象的思維，而且是離散的抽象過程。在這里，課程組講得細致深入，并給學生留下消化吸收的時間。
有限狀態(tài)自動機最主要的表現(xiàn)形式是狀態(tài)轉(zhuǎn)換圖。在講解這部分內(nèi)容時，課程組利用今天的計算機繪圖語言dot，并結(jié)合Graphviz繪圖環(huán)境，引導學生通過程序設(shè)計的辦法讓計算機輕松繪制表現(xiàn)力強的狀態(tài)轉(zhuǎn)換圖。這一過程既訓練了學生對正則表達式的讀取、理解，又利用自動機的構(gòu)造方法進行了形式化描述，最后通過程序設(shè)計達到自動出圖的效果，形成了教與學的閉環(huán)。
利用棧進行簡單左右括號匹配的算法是學生已經(jīng)掌握的算法技能，到了研究生階段，通過進一步學習，學生開始了解采用下推自動機進行括號匹配的字符串檢測也是不錯的便利方式。老師在教學中引導學生進一步考慮括號的嵌套層數(shù)，建立對“廣義表”表達深度的等價關(guān)系，引申出下推自動機棧的最大使用深度對應(yīng)的深度信息。這是一個循序漸進的過程，課程組通過“元認知”推廣到一般情形的教學方法，使學生的接受度大大提高。
在教學方法上，課程組還把線上線下學習結(jié)合起來，學生可以在線上預(yù)先學習基本知識，了解專業(yè)術(shù)語，思考自動機的一般理論和方法。線下課堂教學重在闡述難點和要點，特別是對各自動機的構(gòu)造過程、相關(guān)的算法思想進行深入解析，重在課堂交互和深入研討，引導學生思考，保持課堂教學的流暢度。老師還通過對學習過程的設(shè)計，督促學生對基本知識點透徹掌握，引導學生不要把注意放在奇、難、怪的題目上。
“我們的目標是培養(yǎng)學生掌握文法、產(chǎn)生語言，利用三大自動機接收語言，進一步利用自動機進行原始基礎(chǔ)的1-進制、2-進制四則運算?！敝芤婷窠淌谡f，“我期望這門課程不僅讓學生掌握三大自動機的構(gòu)造，更要引導學生用心體會幾十年來計算機學人定義和發(fā)明各類自動機的心路歷程，為研究生樹立科技創(chuàng)新的勇氣和路徑參考！”
2018級研究生張旭表示，“在研究生一年級期間，懷揣著對人工智能理論和形式語言的熱情學習了這門課程。老師講課很幽默，能把比較困難的問題通俗地解釋給同學們?！?019級研究生余紅表示，“老師上課講解知識點詳細透徹，對難以理解的地方會深入分析，努力讓學生學懂弄通?！?/span>
“講課首先要有趣，并激發(fā)學生的興趣！”余盛季副教授表示，課程組一直在努力引導學生掌握問題求解的思想和方法，領(lǐng)略理論在高度抽象和形式化下的優(yōu)美和樂趣，使這些枯燥的內(nèi)容鮮活起來，使學生自己能夠創(chuàng)造“思路”和“想法”。
為此，課程組逐步將科學思維過程融入學生的知識結(jié)構(gòu)之中，引導學生通過比較、觀察，把新法則納入到原有法則系統(tǒng)中，構(gòu)成緊密聯(lián)系和融匯貫通的知識網(wǎng)絡(luò)；在課堂互動中，善于針對學生情況，提出啟發(fā)性的問題，讓學生主動思考、理解、掌握問題要點，并培養(yǎng)學生分析問題和解決問題的能力。
課程組很重視“課程思政”建設(shè)，引導學生塑造正確的世界觀、人生觀、價值觀。而越接近專業(yè)性的思政教育，越能打動學生的內(nèi)心。
在回顧有限自動機的發(fā)展歷程時，課程組不僅講圖靈、喬姆斯基、巴赫等為機器識別語言及早期人工智能的發(fā)展作出過突出貢獻的科學大家，引導學生感受他們的創(chuàng)新思維和科學精神，也著重講述姚期智院士等最近20年作出重要學術(shù)貢獻的華人科學家的故事，增強同學們追求卓越、攀登高峰的信心。
提出“Dolev-Yao模型”的姚期智院士，用形式化模型討論分析密碼協(xié)議的安全性，并首次證明了“量子圖靈機模型”與“量子電路模型”的等價性，為圖靈機的現(xiàn)實應(yīng)用找到了理論依據(jù)。
“可以預(yù)見，未來在科學領(lǐng)域?qū)⒂懈嗟闹袊茖W家走在時代前列。”課程組老師鼓勵同學們，要從姚期智院士等科學家的奮斗歷程中汲取力量，勇敢迎接挑戰(zhàn)，砥礪奮進、勇毅前行。
陳文宇教授在課堂上推導證明
學生在課堂上認真聽講
課堂上講解重點難點內(nèi)容“圖靈機”
周益民教授在課堂授課
余盛季副教授與學生互動
浸潤學生心靈，為國鑄魂育人
