《形式語言與自動機理論（第2版）》是2012年清華大學出版社出版的圖書。
基本介紹
- 書名：形式語言與自動機理論（第2版）
- ISBN：9787302149705
- 定價：35元
- 出版社：清華大學出版社
- 出版時間：2012年
- 裝幀：平裝
圖書簡介,目錄,
圖書簡介
形式語言與自動機理論是計算機科學與技術專業的一門重要課程。本書是作者結合其20餘年來在大學講授該門課程的經驗和體會，選擇和組織有關內容撰寫而成。不僅含有有關正則語言、上下文無關語言的文法、識別模型及其性質、圖靈機的基本知識，更涉及到本學科方法論中所包含的3個學科形態。其內容特點是抽象和形式化，既有嚴格的理論證明，又具有很強的構造性，從而培養學生的形式化描述和抽象思維能力，使學生了解和初步掌握“問題、形式化、自動化（計算機化）”的解題思路。為了便於學生對內容的掌握，附錄A還給出了建議的教學設計。
目錄
第1章緒論1
1.1集合的基礎知識2
1.1.1集合及其表示2
1.1.2集合之間的關係5
1.1.3集合的運算6
1.2關係12
1.2.1二元關係12
1.2.2等價關係與等價類13
1.2.3關係的合成14
1.2.4遞歸定義與歸納證明15
1.2.5關係的閉包18
1.3圖19
1.3.1無向圖19
1.3.2有向圖21
1.3.3樹23
1.4語言24
1.4.1什麼是語言24
1.4.2形式語言與自動機理論的產生與作用25
1.4.3基本概念28
1.5小結35
習題35
第2章文法42
2.1啟示43
2.2形式定義48
2.3文法的構造58
2.4文法的喬姆斯基體系68
2.5空語句79
2.6小結82
習題82
第3章有窮狀態自動機86
3.1語言的識別86
3.2有窮狀態自動機89
3.3不確定的有窮狀態自動機102
3.3.1作為對DFA的修改102
3.3.2NFA的形式定義104
3.3.3NFA與DFA等價106
3.4帶空移動的有窮狀態自動機110
3.5FA是正則語言的識別器115
3.5.1FA與右線性文法115
3.5.2FA與左線性文法120
3.6FA的一些變形122
3.6.1雙向有窮狀態自動機122
3.6.2帶輸出的FA123
3.7小結125
習題126
第4章正則表達式131
4.1啟示131
4.2正則表達式的形式定義133
4.3正則表達式與FA等價135
4.3.1正則表達式到FA的等價變換135
4.3.2正則語言可以用正則表達式表示144
4.4正則語言等價模型的總結150
4.5小結152
習題153
第5章正則語言的性質156
5.1正則語言的泵引理156
5.2正則語言的封閉性162
5.3MyhillNerode定理與DFA的極小化170
5.3.1MyhillNerode定理170
5.3.2DFA的極小化180
5.4關於正則語言的判定算法189
5.5小結190
習題191
第6章上下文無關語言194
6.1上下文無關文法195
6.1.1上下文無關文法的派生樹195
6.1.2二義性202
6.1.3自頂向下的分析和自底向上的分析205
6.2上下文無關文法的化簡207
6.2.1去無用符號208
6.2.2去ε產生式212
6.2.3去單一產生式組216
6.3喬姆斯基範式219
6.4格雷巴赫範式223
6.5自嵌套文法229
6.6小結230
習題230
第7章下推自動機235
7.1基本定義235
7.2PDA與CFG等價242
7.2.1PDA用空棧接受和用終止狀態接受等價243
7.2.2PDA與CFG等價246
7.3小結257
習題257
第8章上下文無關語言的性質260
8.1上下文無關語言的泵引理260
8.2上下文無關語言的封閉性267
8.3上下文無關語言的判定算法273
8.3.1L空否的判定273
8.3.2L是否有窮的判定274
8.3.3x是否為L的句子的判定276
8.4小結278
習題278
第9章圖靈機280
9.1基本概念281
9.1.1基本圖靈機282
9.1.2圖靈機作為非負整函式的計算模型289
9.1.3圖靈機的構造293
9.2圖靈機的變形300
9.2.1雙向無窮帶圖靈機300
9.2.2多帶圖靈機304
9.2.3不確定的圖靈機306
9.2.4多維圖靈機308
9.2.5其他圖靈機310
9.3通用圖靈機313
9.4幾個相關的概念315
9.4.1可計算性315
9.4.2P與NP相關問題316
9.5小結316
習題317
第10章上下文有關語言320
10.1圖靈機與短語結構文法的等價性320
10.2線性有界自動機及其與上下文有關文法的等價性323
10.3小結325
習題325
附錄A教學設計327
附錄B縮寫符號338
辭彙索引340
參考文獻348
