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

《形式語言與自動機理論教學參考書（第4版）》是2023年6月1日清華大學出版社出版的圖書，作者：蔣宗禮。

基本介紹

• 中文名：形式語言與自動機理論教學參考書（第4版）
• 作者：蔣宗禮
• 出版時間：2023年6月1日
• 出版社：清華大學出版社
• ISBN：9787302636267
• 定價：48 元

出版信息

作者：蔣宗禮

定價：48元

印次：4-1

ISBN：9787302636267

出版日期：2023.06.01

印刷日期：2023.06.09

內容簡介

本書作為《形式語言與自動機理論（第4版）》（主教材）的配套教學輔導用書，按照主教材的結構編寫而成。本書包括有關內容的講解、學習要點、問題分析、求解思路和方法、注意事項。考慮到該課程習題求解具有相當的難度，以及給出全部習題解答又不利於學生學習，本書只給出了典型習題的解析。為了引導讀者及時總結學習內容，按照小節給出知識點和主要內容解讀，為讀者學習和掌握主教材中的知識點和問題求解方法，體會問題求解的核心思想提供幫助，對教師和學生來說，閱讀這些內容都是很有意義的。

圖書目錄

目錄CONTENTS

第1章緒論1

1.1集合的基礎知識2

1.1.1集合及其表示2

1.1.2集合之間的關係3

1.1.3集合的運算4

1.2關係5

1.2.1二元關係5

1.2.2遞歸定義與歸納證明6

1.2.3關係的閉包6

1.3圖7

1.3.1無向圖7

1.3.2有向圖8

1.3.3樹8

1.4語言9

1.4.1什麼是語言9

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

1.4.3基本概念11

1.5小結14

1.6典型習題解析14

第2章文法20

2.1啟示21

2.2形式定義22

2.3文法的構造26

2.4文法的喬姆斯基體系29

2.5空語句32

2.6小結33

2.7典型習題解析33

第3章有窮狀態自動機45

3.1語言的識別46

3.2有窮狀態自動機46

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

3.3.1作為對DFA的修改51

3.3.2NFA的形式定義51

3.3.3NFA與DFA等價52

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

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

3.5.1FA與右線性文法57

3.5.2FA與左線性文法58

3.6FA的一些變形60

3.6.1雙向有窮狀態自動機60

3.6.2帶輸出的FA61

3.7小結62

3.8典型習題解析63

第4章正則表達式70

4.1啟示70

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

4.3正則表達式與FA等價73

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

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

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

4.5小結78

4.6典型習題解析79

第5章正則語言的性質83

5.1正則語言的泵引理84

5.2正則語言的封閉性85

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

5.3.1MyhillNerode 定理89

5.3.2DFA的極小化93

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

5.5小結96

5.6典型習題解析96

第6章上下文無關語言103

6.1上下文無關文法104

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

6.1.2二義性107

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

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

6.2.1去無用符號110

6.2.2去ε產生式113

6.2.3去單一產生式116

6.3喬姆斯基範式117

6.4格雷巴赫範式119

6.5自嵌套文法122

6.6小結123

6.7典型習題解析123

第7章下推自動機127

7.1基本定義128

7.2PDA與CFG等價130

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

7.2.2PDA與CFG等價131

7.3小結133

7.4典型習題解析134

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

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

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

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

8.3.1L空否的判定147

8.3.2L是否有窮的判定147

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

8.4小結150

8.5典型習題解析150

第9章圖靈機152

9.1基本概念153

9.1.1基本圖靈機153

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

9.1.3圖靈機的構造157

9.2圖靈機的變形160

9.2.1雙向無窮帶圖靈機160

9.2.2多帶圖靈機163

9.2.3不確定的圖靈機164

9.2.4多維圖靈機165

9.2.5其他圖靈機166

9.3通用圖靈機168

9.4幾個相關的概念170

9.4.1可計算性170

9.4.2P與NP相關問題170

9.5小結171

9.6典型習題解析171

第10章上下文有關語言183

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

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

10.3小結187

10.4典型習題解析187

第11章內容歸納190

11.1文法與語言190

11.2正則語言190

11.3上下文無關語言191

11.4圖靈機192

11.5上下文有關語言193

第12章教學設計194

12.1概述194

12.1.1基本描述194

12.1.2教學定位194

12.1.3教學目標195

12.1.4知識點與學時分配196

12.2課堂講授198

12.2.1重點與難點198

12.2.2講授中應注意的方法等問題203

12.3作業205

12.3.1指導思想205

12.3.2關於大作業和實驗205

12.4課程考試與成績評定205

12.4.1成績評定205

12.4.2考題設計207

參考文獻209