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

《形式語言與自動機理論教學參考書（第2版）》是2012年清華大學出版社出版的圖書。

基本介紹

• 書名：形式語言與自動機理論教學參考書（第2版）
• ISBN：9787302149712
• 定價：25元
• 出版社：清華大學出版社
• 出版時間：2012-3-9
• 裝幀：平裝

圖書簡介

本書根據作者對計算機科學與技術專業教育特點的理解和“21世紀大學本科計算機專業系列教材”編寫的總體要求，作為《形式語言與自動機理論（第2版）》（主教材）一書的配套教學輔導用書，按照主教材的結構編寫而成。本書包括有關內容的講解、學習要點、問題分析、求解思路和方法、注意事項、典型習題的解析等內容，並且按照小節給出知識點和主要內容解讀。為讀者學習和掌握主教材中的知識點和問題求解方法，體會問題求解的核心思想提供幫助，對教師和學生來說，閱讀這些內容都是很有意義的。

目錄

第1章緒論1

1.1集合的基礎知識2

1.1.1集合及其表示2

1.1.2集合之間的關係3

1.1.3集合的運算4

1.2關係6

1.2.1二元關係6

1.2.2遞歸定義與歸納證明7

1.2.3關係的閉包7

1.3圖8

1.3.1無向圖8

1.3.2有向圖9

1.3.3樹10

1.4語言11

1.4.1什麼是語言11

1.4.2形式語言與自動機理論的產生與作用12

1.4.3基本概念14

1.5小結17

1.6典型習題解析17

第2章文法24

2.1啟示25

2.2形式定義27

2.3文法的構造31

2.4文法的喬姆斯基體系35

2.5空語句39

2.6小結40

2.7典型習題解析41

第3章有窮狀態自動機54

3.1語言的識別55

3.2有窮狀態自動機55

3.3不確定的有窮狀態自動機61

3.3.1作為對DFA的修改61

3.3.2NFA的形式定義61

3.3.3NFA與DFA等價63

3.4帶空移動的有窮狀態自動機66

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

3.5.1FA與右線性文法68

3.5.2FA與左線性文法70

3.6FA的一些變形72

3.6.1雙向有窮狀態自動機72

3.6.2帶輸出的FA73

3.7小結75

3.8典型習題解析76

第4章正則表達式84

4.1啟示85

4.2正則表達式的形式定義85

4.3正則表達式與FA等價87

4.3.1正則表達式到FA的等價變換87

4.3.2正則語言可以用正則表達式表示90

4.4正則語言等價模型的總結92

4.5小結94

4.6典型習題解析95

第5章正則語言的性質99

5.1正則語言的泵引理100

5.2正則語言的封閉性101

5.3Myhill\|Nerode定理與DFA的極小化106

5.3.1Myhill\|Nerode定理106

5.3.2DFA的極小化111

5.4關於正則語言的判定算法113

5.5小結114

5.6典型習題解析115

第6章上下文無關語言123

6.1上下文無關文法124

6.1.1上下文無關文法的派生樹125

6.1.2二義性128

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

6.2上下文無關文法的化簡131

6.2.1去無用符號132

6.2.2去ε\|產生式136

6.2.3去單一產生式139

6.3喬姆斯基範式140

6.4格雷巴赫範式142

6.5自嵌套文法146

6.6小結147

6.7典型習題解析148

第7章下推自動機152

7.1基本定義153

7.2PDA與CFG等價155

7.2.1PDA用空棧接受和用終止狀態接受等價155

7.2.2PDA與CFG等價157

7.3小結159

7.4典型習題解析160

第8章上下文無關語言的性質167

8.1上下文無關語言的泵引理168

8.2上下文無關語言的封閉性171

8.3上下文無關語言的判定算法175

8.3.1L空否的判定175

8.3.2L是否有窮的判定176

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

8.4小結179

8.5典型習題解析179

第9章圖靈機182

9.1基本概念183

9.1.1基本圖靈機184

9.1.2圖靈機作為非負整函式的計算模型188

9.1.3圖靈機的構造189

9.2圖靈機的變形192

9.2.1雙向無窮帶圖靈機193

9.2.2多帶圖靈機196

9.2.3不確定的圖靈機198

9.2.4多維圖靈機199

9.2.5其他圖靈機200

9.3通用圖靈機203

9.4幾個相關的概念204

9.4.1可計算性204

9.4.2P與NP相關問題205

9.5小結206

9.6典型習題解析206

第10章上下文有關語言220

10.1圖靈機與短語結構文法的等價性220

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

10.3小結225

10.4典型習題解析225

第11章內容歸納229

11.1文法與語言229

11.2正則語言229

11.3上下文無關語言230

11.4圖靈機231

11.5上下文有關語言232

第12章教學設計233

12.1概述233

12.2課程內容體系234

12.2.1課程的基本描述234

12.2.2教學定位235

12.2.3知識點與學時分配236

12.3講授提示238

12.3.1重點與難點238

12.3.2講授中應注意的方法等問題242

12.4習題與實驗243

12.4.1指導思想243

12.4.2關於大作業和實驗243

12.5考試與成績記載244

12.5.1成績評定244

12.5.2考題設計244

參考文獻246