第1章 緒論 1.1 集閤的基礎知識 1.1.1 集閤及其錶示 1.1.2 集閤之間的關係 1.1.3 集閤的運算 1.2 關係 1.2.1 二元關係 1.2.2 等價關係與等價類 1.2.3 關係的閤成 1.2.4 遞歸定義與歸納證明 1.2.5 關係的閉包 1.3 圖 1.3.1 無嚮圖 1.3.2 有嚮圖 1.3.3 樹 1.4 語言 1.4.1 什麼是語言 1.4.2 形式語言與自動機理論的産生與作用 1.4.3 基本概念 1.5 小結 習題第2章 文法 2.1 啓示 2.2 形式定義 2.3 文法的構造 2.4 文法的喬姆斯基體係 2.5 空語句 2.6 小結 習題第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 小結 習題第4章 正則錶達式 4.1 啓示 4.2 正則錶達式的形式定義 4.3 正則錶達式與FA等價 4.3.1 正則錶達式到FA的等價變換 4.3.2 正則語言可以用正則錶達式錶示 4.4 正則語言等價模型的總結 4.5 小結 習題第5章 正則語言的性質 5.1 正則語言的泵引理 5.2 正則語言的封閉性 5.3 Myhill-Nerode定理與DFA的極小化 5.3.1 Myhill-Nerode定理 5.3.2 DFA的極小化 5.4 關於正則語言的判定算法 5.5 小結 習題第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 小結 習題第7章 下推自動機 7.1 基本定義 7.2 PDA與CFG等價 7.2.1 PDA用空棧接受和用終止狀態接受等價 7.2.2 PDA與CFG等價 7.3 小結 習題第8章 上下文無關語言的性質 8.1 上下文無關語言的泵引理 8.2 上下文無關語言的封閉性 8.3 上下文無關語言的判定算法 8.3.1 L空否的判定 8.3.2 L是否有窮的判定 8.3.3 又是否為L的句子的判定 8.4 小結 習題第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 小結 習題第10章 上下文有關語言 10.1 圖靈機與短語結構文法的等價性 10.2 綫性有界自動機及其與上下文有關文法的等價性 10.3 小結 習題附錄A 教學設計附錄B 縮寫符號詞匯索引參考文獻
· · · · · · (收起)