形式語言與自動機(jī)理論（第4版）

第1章緒論1

1.1集合的基礎(chǔ)知識2

1.1.1集合及其表示2

1.1.2集合之間的關(guān)系4

1.1.3集合的運(yùn)算5

1.2關(guān)系10

1.2.1二元關(guān)系10

1.2.2等價關(guān)系與等價類11

1.2.3關(guān)系的合成12

1.2.4遞歸定義與歸納證明13

1.2.5關(guān)系的閉包15

1.3圖16

1.3.1無向圖16

1.3.2有向圖17

1.3.3樹19

1.4語言20

1.4.1什么是語言20

1.4.2形式語言與自動機(jī)理論的產(chǎn)生與作用21

1.4.3基本概念23

1.5小結(jié)29

習(xí)題29第2章文法36

2.1啟示37

2.2形式定義39

2.3文法的構(gòu)造47

2.4文法的喬姆斯基體系55

2.5空語句65

2.6小結(jié)67

習(xí)題68第3章有窮狀態(tài)自動機(jī)71

3.1語言的識別71

3.2有窮狀態(tài)自動機(jī)73

3.3不確定的有窮狀態(tài)自動機(jī)84

3.3.1作為對DFA的修改84

3.3.2NFA的形式定義86

3.3.3NFA與DFA等價92

3.4帶空移動的有窮狀態(tài)自動機(jī)96

3.5FA是正則語言的識別器100

3.5.1FA與右線性文法100

3.5.2FA與左線性文法104

3.6FA的一些變形105

3.6.1雙向有窮狀態(tài)自動機(jī)105

3.6.2帶輸出的FA107

3.7小結(jié)108

習(xí)題108目錄形式語言與自動機(jī)理論(第4版)第4章正則表達(dá)式114

4.1啟示114

4.2正則表達(dá)式的形式定義115

4.3正則表達(dá)式與FA等價117

4.3.1正則表達(dá)式到FA的等價變換117

4.3.2正則語言可以用正則表達(dá)式表示125

4.4正則語言等價模型的總結(jié)130

4.5小結(jié)131

習(xí)題132第5章正則語言的性質(zhì)134

5.1正則語言的泵引理134

5.2正則語言的封閉性139

5.3MyhillNerode定理與DFA的極小化145

5.3.1MyhillNerode定理146

5.3.2DFA的極小化154

5.4關(guān)于正則語言的判定算法161

5.5小結(jié)163

習(xí)題163第6章上下文無關(guān)語言166

6.1上下文無關(guān)文法166

6.1.1上下文無關(guān)文法的派生樹167

6.1.2二義性172

6.1.3自頂向下的分析和自底向上的分析175

6.2上下文無關(guān)文法的化簡177

6.2.1去無用符號178

6.2.2去ε產(chǎn)生式181

6.2.3去單一產(chǎn)生式組184

6.3喬姆斯基范式187

6.4格雷巴赫范式190

6.5自嵌套文法195

6.6小結(jié)196

習(xí)題196第7章下推自動機(jī)200

7.1基本定義200

7.2PDA與CFG等價206

7.2.1PDA用空棧接受和用終止?fàn)顟B(tài)接受等價206

7.2.2PDA與CFG等價209

7.3小結(jié)218

習(xí)題219第8章上下文無關(guān)語言的性質(zhì)221

8.1上下文無關(guān)語言的泵引理221

8.2上下文無關(guān)語言的封閉性227

8.3上下文無關(guān)語言的判定算法232

8.3.1L空否的判定232

8.3.2L是否有窮的判定233

8.3.3x是否為L的句子的判定234

8.4小結(jié)236

習(xí)題236第9章圖靈機(jī)238

9.1基本概念239

9.1.1基本圖靈機(jī)239

9.1.2圖靈機(jī)作為非負(fù)整函數(shù)的計算模型246

9.1.3圖靈機(jī)的構(gòu)造248

9.2圖靈機(jī)的變形255

9.2.1雙向無窮帶圖靈機(jī)255

9.2.2多帶圖靈機(jī)258

9.2.3不確定的圖靈機(jī)260

9.2.4多維圖靈機(jī)261

9.2.5其他圖靈機(jī)263

9.3通用圖靈機(jī)265

9.4幾個相關(guān)的概念267

9.4.1可計算性267

9.4.2P與NP相關(guān)問題267

9.5小結(jié)268

習(xí)題268第10章上下文有關(guān)語言272

10.1圖靈機(jī)與短語結(jié)構(gòu)文法的等價性272

10.2線性有界自動機(jī)及其與上下文有關(guān)文法的等價性275

10.3小結(jié)276

習(xí)題277附錄A教學(xué)設(shè)計278

A.1課程概述278

A.1.1基本描述278

A.1.2教學(xué)定位278

A.1.3教學(xué)目標(biāo)279

A.1.4知識點與學(xué)時分配280

A.2課堂講授282

A.2.1重點與難點282

A.2.2講授中應(yīng)注意的方法等問題287

A.3作業(yè)289

A.3.1指導(dǎo)思想289

A.3.2關(guān)于大作業(yè)和實驗289

A.4課程考試與成績評定289

A.4.1成績評定289

A.4.2考題設(shè)計291附錄B縮寫符號293詞匯索引295參考文獻(xiàn)302