形式語言與自動機理論教學參考書(第3版)

形式語言與自動機理論教學參考書(第3版)

《形式語言與自動機理論教學參考書》是2013年清華大學出版社出版的圖書,作者是蔣宗禮。

基本介紹

  • 書名:形式語言與自動機理論教學參考書(第3版)
  • 作者:蔣宗禮
  • ISBN:9787302317814
  • 定價:26元
  • 出版社:清華大學出版社
  • 出版時間:2013-5-8
  • 裝幀:平裝
圖書簡介,圖書目錄,

圖書簡介

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

圖書目錄

第1章緒論11.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版)[]第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
第12章教學設計194
12.1概述194
12.2課程內容體系195
12.2.1課程的基本描述195
12.2.2教學定位195
12.2.3知識點與學時分配196
12.3講授提示198
12.3.1重點與難點198
12.3.2講授中應注意的方法等問題201
12.4習題與實驗202
12.4.1指導思想202
12.4.2關於大作業和實驗202
12.5考試與成績記載202
12.5.1成績評定202
12.5.2考題設計203
參考文獻204

相關詞條

熱門詞條

聯絡我們