本站非官方網站，信息完全免費，僅供參考，不收取任何費用，具體請以官網公布為準！
063403     形式語言與自動機                              32學時/ 2學分
英文譯名：Formal Language and Automata
適用領域：計算機軟件與理論、計算機應用技術
開課單位：計算機科學與技術學院
教學目的：形式語言和自動機理論是理論計算機科學的重要分支，在計算機科學的許多領域起著理論基礎和方法論的作用，特別是對程序語言的設計、編譯理論與技術、模型檢測、模式識別和自然語言理解等領域起了重要促進作用。通過對本課程的學習，研究生能夠從文法和識別器的角度，掌握各類文法和自動機設計的方法和技術，提高問題的形式化描述和抽象思維能力，理解并實踐“問題、形式化描述、自動化（計算機化）”的解決問題過程。
預備知識或先修課程要求：離散數學或相關知識。
教學方式及學時分配：課堂授課32學時。
 

學時	教學內容	教學方式
2	課程概述、語言和句子的概念	授課
2	文法的形式定義、文法的構造	授課
2	文法的喬姆斯基體系、空句子	授課
2	語言的識別、有窮狀態自動機	授課
2	不確定的有窮狀態自動機、帶空移動的有窮狀態自動機	授課
2	FA是正則語言的識別器、FA的變形	授課
2	正則表達式	授課
2	正則語言等價模型的總結、正則語言的性質	授課
2	正則語言的泵引理、正則語言的封閉性	授課
2	Myhill-Nerode定理與DFA的極小化	授課
2	關于正則語言的判定算法、上下文無關文法及化簡	授課
2	喬姆斯基范式、格雷巴赫方式、自嵌套文法	授課
2	下推自動機的基本定義、PDA與CFG等價	授課
2	上下文無關語言的性質、泵引理和封閉性	授課
2	上下文無關語言的判定算法、圖靈機的基本概念	授課
2	圖靈機的變形、幾個相關的概念、課程總結	授課

 
教學主要內容以及對學生的要求：
教學主要內容是形式語言與自動機方面的主要理論成果和應用實例。
要求研究生系統地掌握各類文法和自動機設計的方法和技術，形成問題的形式化描述和抽象思維的能力。
內容摘要：教學內容以四類形式語言和相應的自動機為主線，討論形式語言與自動機方面的主要理論成果和應用實例。主要包括：介紹形式語言及其相關概念，按喬姆斯基體系討論四類形式文法。詳細介紹有窮自動機的概念、各種變形及其應用；介紹正則表達式的概念，討論各種等價變換方法，并論述正則表達式和有窮自動機的關系；對正則語言的各種表現形式加以總結，論述正則語言的各種重要性質，并重點討論有窮自動機的極小化問題。介紹上下文無關文法的基本概念和性質，引入下推自動機的概念，并論證下推自動機和上下文無關文法的等價性。介紹圖靈機的基本概念，給出它的基本模型和各種變形，用實例表明圖靈機具有很強的識別能力和計算能力，并說明圖靈機和0型文法的等價性。簡單介紹線性有界自動機，并證明它與上下文有關文法等價性。對各語言類之間的關系做一總結。
考核方式：閉卷考試，平時作業等占一定比例（不超過30%）。
課程主要教材：形式語言與自動機理論(第2版) .蔣宗禮.清華大學出版社,2007
主要參考書目：
[1] 自動機理論、語言和計算導論(原書第3版).（美）霍普克羅夫特著.機械工業出版社，2008
[2] 計算理論導引(第2版) .(美)西普塞.機械工業出版社，2006
[3] 形式語言與自動機. 陳有祺.機械工業出版社，2008
學習文檔  http://xjuit.com/wenku/