形式語言與自動機理論(第3版)

形式語言與自動機理論(第3版)

《形式語言與自動機理論(第3版)》是2013年清華大學出版社出版的圖書,作者是蔣宗禮、姜守旭。

基本介紹

  • 中文名:形式語言與自動機理論(第3版)
  • 作者:蔣宗禮、姜守旭
  • 出版社:清華大學出版社
  • 出版時間:2013年5月1日
  • 定價:36 元
  • ISBN:9787302318026
內容簡介,圖書目錄,

內容簡介

本書是作者結合其近30年來在大學講授該門課程的經驗和體會,選擇和組織有關內容撰寫而成。基於計算機問題求解的需要討論正則語言、上下文無關語言的文法、識別模型及其性質、圖靈機的基本知識。其內容特點是抽象和形式化,既有嚴格的理論證明,又具有很強的構造性。敘述中特別注意引導讀者分析與解決問題,以培養學生的形式化描述和抽象思維能力,使學生了解和初步掌握“問題、形式化、自動化(計算機化)”的解題思路。為了便於學生對內容的掌握,附錄A還給出了建議的教學設計。本書配套出版有《形式語言與自動機理論教學參考書(第3版)》,歸納各章知識點,解讀主要內容,解析典型習題。
形式語言與自動機理論是計算機科學與技術專業的一門重要課程。本書是作者結合其近30年來在大學講授該門課程的經驗和體會,選擇和組織有關內容撰寫而成。基於計算機問題求解的需要討論正則語言、上下文無關語言的文法、識別模型及其性質、圖靈機的基本知識。其內容特點是抽象和形式化,既有嚴格的理論證明,又具有很強的構造性。敘述中特別注意引導讀者分析與解決問題,以培養學生的形式化描述和抽象思維能力,使學生了解和初步掌握“問題、形式化、自動化(計算機化)”的解題思路。為了便於學生對內容的掌握,附錄A還給出了建議的教學設計。本書配套出版有《形式語言與自動機理論教學參考書(第3版)》,歸納各章知識點,解讀主要內容,解析典型習題。

圖書目錄

第1章緒論11.1集合的基礎知識2
1.1.1集合及其表示2
1.1.2集合之間的關係4
1.1.3集合的運算5
1.2關係10
1.2.1二元關係10
1.2.2等價關係與等價類11
1.2.3關係的合成12
1.2.4遞歸定義與歸納證明12
1.2.5關係的閉包15
1.3圖15
1.3.1無向圖16
1.3.2有向圖17
1.3.3樹19
1.4語言20
1.4.1什麼是語言20
1.4.2形式語言與自動機理論的產生與作用21
1.4.3基本概念23
1.5小結28
習題29
第2章文法35
2.1啟示36
2.2形式定義38
2.3文法的構造46
2.4文法的喬姆斯基體系54
2.5空語句64
2.6小結66
習題66目錄形式語言與自動機理論(第3版)第3章有窮狀態自動機70
3.1語言的識別70
3.2有窮狀態自動機72
3.3不確定的有窮狀態自動機83
3.3.1作為對DFA的修改83
3.3.2NFA的形式定義84
3.3.3NFA與DFA等價86
3.4帶空移動的有窮狀態自動機90
3.5FA是正則語言的識別器94
3.5.1FA與右線性文法94
3.5.2FA與左線性文法98
3.6FA的一些變形99
3.6.1雙向有窮狀態自動機100
3.6.2帶輸出的FA101
3.7小結102
習題103
第4章正則表達式108
4.1啟示108
4.2正則表達式的形式定義109
4.3正則表達式與FA等價111
4.3.1正則表達式到FA的等價變換111
4.3.2正則語言可以用正則表達式表示119
4.4正則語言等價模型的總結124
4.5小結126
習題126
第5章正則語言的性質129
5.1正則語言的泵引理129
5.2正則語言的封閉性134
5.3MyhillNerode 定理與DFA的極小化140
5.3.1MyhillNerode 定理140
5.3.2DFA的極小化148
5.4關於正則語言的判定算法156
5.5小結157
習題158
第6章上下文無關語言160
6.1上下文無關文法160
6.1.1上下文無關文法的派生樹161
6.1.2二義性166
6.1.3自頂向下的分析和自底向上的分析169
6.2上下文無關文法的化簡171
6.2.1去無用符號172
6.2.2去ε產生式175
6.2.3去單一產生式組178
6.3喬姆斯基範式181
6.4格雷巴赫範式184
6.5自嵌套文法189
6.6小結190
習題190
第7章下推自動機194
7.1基本定義194
7.2PDA與CFG等價200
7.2.1PDA用空棧接受和用終止狀態接受等價200
7.2.2PDA與CFG等價203
7.3小結212
習題212
第8章上下文無關語言的性質215
8.1上下文無關語言的泵引理215
8.2上下文無關語言的封閉性221
8.3上下文無關語言的判定算法226
8.3.1L空否的判定226
8.3.2L是否有窮的判定227
8.3.3x是否為L的句子的判定 228
8.4小結230
習題230
第9章圖靈機231
9.1基本概念232
9.1.1基本圖靈機232
9.1.2圖靈機作為非負整函式的計算模型239
9.1.3圖靈機的構造241
9.2圖靈機的變形247
9.2.1雙向無窮帶圖靈機247
9.2.2多帶圖靈機250
9.2.3不確定的圖靈機252
9.2.4多維圖靈機253
9.2.5其他圖靈機255
9.3通用圖靈機257
9.4幾個相關的概念259
9.4.1可計算性259
9.4.2P與NP相關問題259
9.5小結260
習題260
第10章上下文有關語言263
10.1圖靈機與短語結構文法的等價性263
10.2線性有界自動機及其與上下文有關文法的等價性266
10.3小結267
習題267
附錄A教學設計269
A.1課程內容體系269
A.1.1基本描述269
A.1.2教學定位269
A.1.3知識點與學時分配270
A.2課程的講授271
A.2.1重點與難點271
A.2.2講授中應注意的方法等問題275
A.3作業276
A.3.1指導思想276
A.3.2關於大作業和實驗276
A.4考試與成績記載276
A.4.1成績評定276
A.4.2考題設計276
附錄B縮寫符號278辭彙索引280
參考文獻287

相關詞條

熱門詞條

聯絡我們