形式語言與自動機理論

前言
第1章　語言及其表示
　1.1　字母表、串和語言
　　1.1.1　字母表
　　1.1.2　串
　　1.1.3　語言
　1.2　文法
　1.3　語言識別器
　習題1
第2章　正規(guī)表達式、正規(guī)文法與有限自動機
　2.1　正規(guī)表達式與正規(guī)集
　2.2　正規(guī)文法和正規(guī)語言
　2.3　有限自動機
　　2.3.1　有限狀態(tài)系統(tǒng)
　　2.3.2　確定的有限自動機
　　2.3.3　不確定的有限自動機
　　2.3.4　帶ε-轉(zhuǎn)換的不確定有限自動機
　2.4　正規(guī)表達式、正規(guī)文法與有限自動機的等價性
　　2.4.1　正規(guī)表達式與有限自動機的等價性
　　2.4.2　正規(guī)文法與有限自動機的等價性
　　2.4.3　把正規(guī)文法和有限自動機轉(zhuǎn)化為正規(guī)表達式方程組求解
　2.5　正規(guī)語言的Pumping引理
　2.6　帶輸出的有限自動機
　　2.6.1　Moore機
　　2.6.2　Mea1y機
　　2.6.3　Moore機同Mea1y機的等價性
　2.7　有限自動機的化簡
　　2.7.1　米希爾-尼羅德定理
　　2.7.2　最簡有限自動機
　　2.7.3　有限自動機的化簡方法
　2.8　正規(guī)表達式和有限自動機的應(yīng)用
　　2.8.1　詞法分析程序
　　2.8.2　文本編輯程序
　　2.8.3　文本搜索與字符串匹配
　　2.8.4　時序電路的分析與設(shè)計
　習題2
第3章　上下文無關(guān)文法與下推自動機
　3.1　上下文無關(guān)文法
　3.2　推導(dǎo)樹
　　3.2.1　推導(dǎo)樹的定義和例子
　　3.2.2　推導(dǎo)樹與推導(dǎo)的關(guān)系
　　3.2.3　最左推導(dǎo)與最右推導(dǎo)
　　3.2.4　上下文無關(guān)文法的歧義性
　3.3　上下文無關(guān)文法的化簡
　　3.3.1　無用字符
　　3.3.2　空產(chǎn)生式
　　3.3.3　單產(chǎn)生式
　3.4　喬姆斯基范式和格雷巴赫范式
　　3.4.1　喬姆斯基范式
　　3.4.2　格雷巴赫范式
　3.5　上下文無關(guān)語言的固有歧義性
　3.6　上下文無關(guān)文法的應(yīng)用
　　3.6.1　語法分析程序
　　3.6.2　語法分析程序生成器
　　3.6.3　超文本標記語言
　　3.6.4　可擴展標記語言
　3.7　下推自動機
　　3.7.1　下推自動機的基本定義
　　3.7.2　兩種不同方式接受語言的下推自動機的等價性
　　3.7.3　確定的下推自動機
　3.8　上下文無關(guān)文法與下推自動機的等價性
　3.9　上下文無關(guān)語言的Pumping引理
　習題3
第4章　圖靈機
第5章　喬姆斯基文法體系
第6章　語言的運算與封閉性質(zhì)
第7章　判定問題與不可判定性
第8章　確定的上下文無關(guān)語言
參考文獻