形式語言與自動機理論（第2版）

第1章 緒論
　1.1 集合的基礎(chǔ)知識
　　1.1.1 集合及其表示
　　1.1.2 集合之間的關(guān)系
　　1.1.3 集合的運算
　1.2 關(guān)系
　　1.2.1 二元關(guān)系
　　1.2.2 等價關(guān)系與等價類
　　1.2.3 關(guān)系的合成
　　1.2.4 遞歸定義與歸納證明
　　1.2.5 關(guān)系的閉包
　1.3 圖19
　　1.3.1 無向圖
　　1.3.2 有向圖
　　1.3.3 樹
　1.4 語言
　　1.4.1 什么是語言
　　1.4.2 形式語言與自動機理論的產(chǎn)生與作用
　　1.4.3 基本概念
　1.5 小結(jié)
　習題
第2章 文法
　2.1 啟示
　2.2 形式定義
　2.3 文法的構(gòu)造
　2.4 文法的喬姆斯基體系
　2.5 空語句
　2.6 小結(jié)
　習題82
第3章 有窮狀態(tài)自動機
　3.1 語言的識別
　3.2 有窮狀態(tài)自動機
　3.3 不確定的有窮狀態(tài)自動機
　　3.3.1 作為對DFA的修改
　　3.3.2 NFA的形式定義
　　3.3.3 NFA與DFA等價
　3.4 帶空移動的有窮狀態(tài)自動機
　3.5 FA是正則語言的識別器
　　3.5.1 FA與右線性文法
　　3.5.2 FA與左線性文法
　3.6 FA的一些變形
　　3.6.1 雙向有窮狀態(tài)自動機
　　3.6.2 帶輸出的FA
　3.7 小結(jié)
　習題
第4章 正則表達式
　4.1 啟示
　4.2 正則表達式的形式定義
　4.3 正則表達式與FA等價
　　4.3.1 正則表達式到FA的等價變換
　　4.3.2 正則語言可以用正則表達式表示
　4.4 正則語言等價模型的總結(jié)
　4.5 小結(jié)
　習題153
第5章 正則語言的性質(zhì)
　5.1 正則語言的泵引理
……
第6章 上下文無關(guān)語言
第7章 下推自動機
第8章 上下文無關(guān)語言的性質(zhì)
第9章 圖靈機
第10章 上下文有關(guān)語言
附錄A 教學(xué)設(shè)計
附錄B 縮寫符號
詞匯索引
參考文獻