形式語言與自動機理論教學參考書(第3版)（簡體書）

《“十二五”普通高等教育本科國家級規劃教材：形式語言與自動機理論教學參考書（第3版）》作為《形式語言與自動機理論（第3版）》（主教材）的配套教學輔導用書，按照主教材的結構編寫而成。《“十二五”普通高等教育本科國家級規劃教材：形式語言與自動機理論教學參考書（第3版）》包括有關內容的講解、學習要點、問題分析、求解思路和方法、注意事項。考慮到該課程習題求解具有相當的難度，以及給出全部習題解答又不利於學生學習，只給出了典型習題的解析。為了引導讀者及時總結學習內容，按照小節給出知識點和主要內容解讀，為讀者學習和掌握主教材中的知識點和問題求解方法，體會問題求解的核心思想提供幫助，對教師和學生來說，閱讀這些內容都是很有意義的。

蔣宗禮，1978年3月至1984年7月在哈爾濱工業大學計算機學科學習，曾到美國，加拿大進修，自1984年起先後在哈爾濱工業大學和北京工業大學主講編譯原理、形式語言與自動機理論、人工神經網絡等課程。國家級教學名師，國家級教學團隊負責人，國家精品課程，國家精品課程、國家精品資源共享課（立項）負責人，主編有國家級精品教材，獲國家教學成果二等獎2項，另有師、航天部優秀青年教師等榮譽稱號。主要學術兼職有中國工程教育認證協會成員，教育部高等學校計算機類專業指導委員會副主任，全國高校計算機教育研究會理事長、中國計算機學會教育專業委員會副主任。

蔣宗禮編著的《形式語言與自動機理論教學參考書(第3版）》共分12章。為了便于閱讀，從第1章到第10章完全與原書結構相對應。第1章回顧在離散數學中學過的本書將要用到的一些基礎知識，為后續的章節做好準備。由于主要是為了復習，所以這里給出的是知識點和應該注意的事項。除最后一節的“形式語言及其相關的基本概念”為新內容外，其他內容都可以由學生自學。第2章到第8章是教學的重點內容，主要討論正則語言和上下文無關語言的文法、自動機描述及其性質。第9章對計算進行介紹，包括一般計算模型圖靈機的概念、構造方法、修改，與計算相關的不可判定性、P\|NP等問題。第10章介紹上下文有關語言。在這些章節中，以知識點、主要內容解讀、典型習題解析的形式，對討論的內容進行歸納和解析。第11章對本書的內容按類進行全面總結。在第12章中安排了教學設計，從總體上討論本課程的講授等問題。

第1章緒論
1.1集合的基礎知識
1.1.1集合及其表示
1.1.2集合之間的關係
1.1.3集合的運算
1.2關係
1.2.1二元關係
1.2.2遞歸定義與歸納證明
1.2.3關係的閉包
1.3圖
1.3.1無向圖
1.3.2有向圖
1.3.3樹
1.4語言
1.4.1什麼是語言
1.4.2形式語言與自動機理論的產生與作用
1.4.3基本概念
1.5小結
1.6典型習題解析

第2章文法
2.1啟示
2.2形式定義
2.3文法的構造
2.4文法的喬姆斯基體系
2.5空語句
2.6小結
2.7典型習題解析

第3章有窮狀態自動機
3.1語言的識別
3.2有窮狀態自動機
3.3不確定的有窮狀態自動機
3.3.1作為對DFA的修改
3.3.2NFA的形式定義
3.3.3NFA與DFA等價
3.4帶空移動的有窮狀態自動機
3.5FA是正則語言的識別器
3.5.1FA與右線性文法
3.5.2FA與左線性文法
3.6FA的一些變形
3.6.1雙向有窮狀態自動機
3.6.2帶輸出的FA
3.7小結
3.8典型習題解析

第4章正則表達式
4.1啟示
4.2正則表達式的形式定義
4.3正則表達式與FA等價
4.3.1正則表達式到FA的等價變換
4.3.2正則語言可以用正則表達式表示
4.4正則語言等價模型的總結
4.5小結
4.6典型習題解析

第5章正則語言的性質
5.1正則語言的泵引理
5.2正則語言的封閉性
5.3Myhill?Nerode定理與DFA的極小化
5.3.1Myhill?Nerode定理
5.3.2DFA的極小化
5.4關於正則語言的判定算法
5.5小結
5.6典型習題解析

第6章上下文無關語言
6.1上下文無關文法
6.1.1上下文無關文法的派生樹
6.1.2二義性
6.1.3自頂向下的分析和自底向上的分析
6.2上下文無關文法的化簡
6.2.1去無用符號
6.2.2去ε?產生式
6.2.3去單一產生式
6.3喬姆斯基範式
6.4格雷巴赫範式
6.5自嵌套文法
6.6小結
6.7典型習題解析

第7章下推自動機
7.1基本定義
7.2PDA與CFG等價
7.2.1PDA用空棧接受和用終止狀態接受等價
7.2.2PDA與CFG等價
7.3小結
7.4典型習題解析

第8章上下文無關語言的性質
8.1上下文無關語言的泵引理
8.2上下文無關語言的封閉性
8.3上下文無關語言的判定算法
8.3.1L空否的判定
8.3.2L是否有窮的判定
8.3.3x是否為L的句子的判定
8.4小結
8.5典型習題解析

第9章圖靈機
9.1基本概念
9.1.1基本圖靈機
9.1.2圖靈機作為非負整函數的計算模型
9.1.3圖靈機的構造
9.2圖靈機的變形
9.2.1雙向無窮帶圖靈機
9.2.2多帶圖靈機
9.2.3不確定的圖靈機
9.2.4多維圖靈機
9.2.5其他圖靈機
9.3通用圖靈機
9.4幾個相關的概念
9.4.1可計算性
9.4.2P與NP相關問題
9.5小結
9.6典型習題解析

第10章上下文有關語言
10.1圖靈機與短語結構文法的等價性
10.2線性有界自動機及其與上下文有關文法的等價性
10.3小結
10.4典型習題解析

第11章內容歸納
11.1文法與語言
11.2正則語言
11.3上下文無關語言
11.4圖靈機

第12章教學設計
12.1概述
12.2課程內容體系
12.2.1課程的基本描述
12.2.2教學定位
12.2.3知識點與學時分配
12.3講授提示
12.3.1重點與難點
12.3.2講授中應注意的方法等問題
12.4習題與實驗
12.4.1指導思想
12.4.2關於大作業和實驗
12.5考試與成績記載
12.5.1成績評定
12.5.2考題設計
參考文獻