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

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

書名:形式語言與自動機理論教學參考書（第3版）

：26.00元

作者:蔣宗禮

齣版社：清華大學齣版社

齣版日期：

ISBN：9787302317814

字數：

頁碼：

版次：3

裝幀：

開本：

商品重量：

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

 第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.2 NFA的形式定義
3.3.3 NFA與DFA等
3.4 帶空移動的有窮狀態自動機
3.5 FA是正則語言的識彆器
3.5.1 FA與右綫性文法
3.5.2 FA與左綫性文法
3.6 FA的一些變形
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.3 Myhill�睳erode定理與DFA的極小化
5.3.1 Myhill�睳erode定理
5.3.2 DFA的極小化
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.2 PDA與CFG等
7.2.1 PDA用空棧接受和用終止狀態接受等
7.2.2 PDA與CFG等
7.3 小結
7.4 典型習題解析

第8章 上下文無關語言的性質
8.1 上下文無關語言的泵引理
8.2 上下文無關語言的封閉性
8.3 上下文無關語言的判定算法
8.3.1 L空否的判定
8.3.2 L是否有窮的判定
8.3.3 x是否為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.2 P與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 考試與成績記載
 

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

 培養創新人纔，對本科教育來講，主要是夯實基礎、訓練思維、養成探索之習慣。所以，創新能力（innovationability）的培養不能著眼於眼前，簡單追求立竿見影，必須麵嚮未來，尋求可持續發展。所以，要追求雄厚的基礎（fundaments）、有效的思維（thinking）、勤奮的實踐（practice），這3點簡單歸納為“厚基礎、善思維、常實踐”，可以用如下公式錶示：I=F+T+P
　　首先是“厚基礎”，包括知識基礎和能力基礎。對計算機類專業人纔來說，重要的理論基礎主要來自於理論課程的學習。認真深入地讀幾本基礎性的書，深入理解其中的內容，使自己的思想水平上升到一個新的高度，是非常必要的。為瞭達到學習知識以提升能力的目的，就要在學習知識的同時，注重對其中蘊含的思想和方法的學習，培養主動探索意識與精神。其次是“善思維”。古人雲：“學而不思則罔，思而不學則殆。”要想將書中的知識轉化成自己的知識和能力，就必須在認真讀書的過程中勤奮地思考。在培養創新思維能力的過程中建立創新意識，形成創新能力。最後，“常實踐”是手段。在實踐中去加深理解，實踐探索。“動手能力”不能是狹義的，它不僅僅簡單地來自於下工廠、進企業、進實驗室的活動，更不是簡單地“編程序”。作為一名科技工作者，“動手”的關鍵在於“動腦”。
　　就計算學科而言，離開瞭理論的指導，就很難有高水平的實踐。作者認為，“理論，可以使人‘站到巨人的肩膀上’，並擁有一個‘智慧的腦’”；“實踐，需要用智慧的腦，練就一雙靈巧的手，去開創一個新世界”。不應該將理論和實踐教學割裂開，要有意識地將它們融在一起，這樣會收到事半功倍的效果。這就是說，既要“動手”又要“動腦”，要用高水平的動腦，去“指揮”高水平的動手，也就是“理性實踐”。而且，不同的專業、不同的課程需要不同形式的實踐。就本課程而言，認真地讀書，思考一些問題，做一些各種難度的練習，就是一種常規的實踐。在這個過程中領悟大師們的思維，從而達到訓練思維、提升思維水平的目的，不斷強化自己探索未知的意識，提升探索的能力。
　　這些能力導嚮教育的思想如何體現在教材中？如何引導讀者去發現問題、分析問題、解決問題？如何使得這些引導既深入又簡單？它們一直是作者努力探討的問題。在本書的寫作中，除瞭敘述基本的知識內容外，還努力進行著問題的分析，從而使這些分析在本書中占有很大的篇幅。建議讀者不要簡單地背定義、定理，要深入地理解，達到能夠用自己的語言錶達它們的程度。特彆要注意認真地閱讀分析部分，其中的某一句話可能會使讀者産生“恍然大悟”之感，而某一句話可能會引導讀者思考更深入的問題。希望讀者能夠仔細地閱讀這些內容，相信會有更多的收獲。