形式語言與自動機理論教學參考書

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

基本介紹

• 書名：形式語言與自動機理論教學參考書
• 作者：蔣宗禮
• 出版社： 清華大學出版社
• 出版時間： 2007

版權資訊

ISBN: 9787302149712

開本： 16

定價: 25.00 元

目錄

第1章 緒論

1.1 集合的基礎知識

1.1.1 集合及其表示

1.1.2 集合之間的關係

1.1.3 集合的運算

1.2 關係

1.2.1 二元關係

1.2.2 遞歸定義與歸納證明

1.2.3 關係的閉包

1.3 圖

1.3.1 無向圖

1.3.2 有向圖

1.3.3 樹

1.4 語言

1.4.1 什麼是語言

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

1.4.3 基本概論

1.5 小結

1.6 典型習題解析

第2章 文法

2.1 啟示

2.2 形式定義

2.3 文法的構造

2.4 文法喬姆基體系

2.5 空語句

2.6 小結

2.7 典型習題解析

第3章 有窮狀態自動機

3.1 語言的識別

3.2 有窮狀態自動機

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

3.3.1 作為對DFA 的修改

3.3.2 NFA的形式定義

3.3.3 NFA與DFA等價

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

3.5 FA是正則語言的識別器

3.5.1 FA與右線性文法

3.5.2 FA與左線性文法

3.6 FA的一些變形

3.6.1 雙向有窮狀態自動機

3.6.2 帶輸出的FA

3.7 小結

3.8 典型題解析

第4章 正則表達式

4.1 啟示

4.2 正則表達式的形式定義

4.3 正則表達式與FA等價

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

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

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

4.5 小結

4.6 典型習題解析

第5章 正則語言的性質

5.1 正則語言的泵引理

5.2 正則語言的封閉性

5.3 Myhill-Nerode定理與DFA的極小化

5.3.1 Myhill-Nerode定理

5.3.2 DFA的極小化

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

5.5 小結

5.6 典型習題解析

第6章 上下文無關語言

6.1 上下文無關文法

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

6.1.2 二義性

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

6.2 上下文無關文法的化簡

6.2.1 去無用符號

6.2.2 去ε-產生式

6.2.3 去單一產生式

6.3 喬姆斯基範式

6.4 格雷巴赫範式

6.5 自嵌套文法

6.6 小結

6.7 典型習題解析

第7章 下推自動機

7.1 基本定義

7.2 PDA與CFG等價

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

7.2.2 PDA與CFG等價

7.3 小結

7.4 典型習題解析

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

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

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

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

8.3.1 L空否判定

8.3.2 L是否有窮的判定

8.3.3 X是否為L的句子的判定

8.4 小結

8.5 典型習題解析

第9章 圖靈機

9.1 基本概念

9.1.1 基本圖靈機

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

9.1.3 圖靈的構造

9.2 圖靈機的變形

9.2.1 雙向無窮帶圖靈機

9.2.2 多帶圖靈機

9.2.3 不確定的圖靈機

9.2.4 多維圖靈機

9.2.5 其他圖靈機

9.3 通用圖靈機

9.4 幾個相關的概念

9.4.1 可計算性

9.4.2 P與NP的相關問題

9.5 小結

9.6 典型習題解析

第10章 上下文有關語言

第11章 內容歸納

第12章 教學設計

參考文獻