形式語言與自動機理論引論

《形式語言與自動機理論引論》是2017年3月清華大學出版社出版的圖書，作者是蔣宗禮、姜守旭。

基本介紹

• 中文名：形式語言與自動機理論引論
• 作者：蔣宗禮、姜守旭
• 出版社：清華大學出版社
• 出版時間：2017年3月
• 定價：39 元
• ISBN：9787302456025

內容簡介

形式語言與自動機理論因其以體現計算學科中模型描述、模型研究和模型計算為問題求解的主要特徵而成為計算機科學與技術、軟體工程、網路空間安全等計算機類學科教育的最重要的內容之一。本書按照我國當前計算機類及相關學科研究生教育實際需求，結合作者30餘年的教學實踐編著而成，以正則語言與上下文無關語言的文法、識別模型及其性質，以及圖靈機基本知識為載體，分9章討論相關內容，力圖強化學生基於模型的建立、研究、處理，實現問題求解的意識，讓學生掌握相應的基本方法，提升解決問題的能力與水平。

本書適合計算機類及相關學科研究生使用，也可以供相關專業高年級本科生、教師和科研人員參考。

圖書目錄

第1章語言與文法1

1.1語言2

1.1.1什麼是語言2

1.1.2形式語言與自動機理論的產生2

1.1.3基本概念3

1.2文法9

1.3文法的構造18

1.4文法的喬姆斯基體系26

1.5空語句36

1.6小結38

習題38

第2章有窮狀態自動機44

2.1語言的識別44

2.2有窮狀態自動機46

2.3不確定的有窮狀態自動機57

2.3.1作為對DFA的修改57

2.3.2NFA的形式定義58

2.3.3NFA與DFA等價60

2.4帶空移動的有窮狀態自動機64

2.5FA是正則語言的識別器68

2.5.1FA與右線性文法68

2.5.2FA與左線性文法72

2.6FA的一些變形73

2.6.1雙向有窮狀態自動機74

2.6.2帶輸出的FA75

2.7小結76

習題77

第3章正則表達式82

3.1啟示82

3.2正則表達式的形式定義83

3.3正則表達式與FA等價85

3.3.1正則表達式到FA的等價變換85

3.3.2正則語言可以用正則表達式表示93

3.4正則語言等價模型的總結98

3.5小結100

習題100

第4章正則語言的性質103

4.1正則語言的泵引理103

4.2正則語言的封閉性108

4.3MyhillNerode定理與DFA的極小化114

4.3.1MyhillNerode定理114

4.3.2DFA的極小化122

4.4關於正則語言的判定算法130

4.5小結131

習題132

形式語言與自動機理論引論第5章上下文無關語言134

5.1上下文無關文法134

5.1.1上下文無關文法的派生樹135

5.1.2二義性140

5.1.3自頂向下的分析和自底向上的分析143

5.2上下文無關文法的化簡145

5.2.1去無用符號146

5.2.2去ε產生式149

5.2.3去單一產生式組152

5.3喬姆斯基範式155

5.4格雷巴赫範式158

5.5自嵌套文法163

5.6小結164

習題164

第6章下推自動機168

6.1基本定義168

6.2PDA與CFG等價174

6.2.1PDA用空棧接受和用終止狀態接受等價174

6.2.2PDA與CFG等價177

6.3小結186

習題186

第7章上下文無關語言的性質189

7.1上下文無關語言的泵引理189

7.2上下文無關語言的封閉性195

7.3上下文無關語言的判定算法200

7.3.1L空否的判定200

7.3.2L是否有窮的判定201

7.3.3x是否為L的句子的判定202

7.4小結204

習題204

第8章圖靈機205

8.1基本概念206

8.1.1基本圖靈機206

8.1.2圖靈機作為非負整函式的計算模型213

8.1.3圖靈機的構造215

8.2圖靈機的變形221

8.2.1雙向無窮帶圖靈機221

8.2.2多帶圖靈機224

8.2.3不確定的圖靈機226

8.2.4多維圖靈機227

8.2.5其他圖靈機229

8.3通用圖靈機231

8.4幾個相關的概念233

8.4.1可計算性233

8.4.2P與NP相關問題233

8.5小結234

習題234

第9章上下文有關語言237

9.1圖靈機與短語結構文法的等價性237

9.2線性有界自動機及其與上下文有關文法的等價性240

9.3小結241

習題241

附錄縮寫符號243

辭彙索引245

參考文獻251