有限自動(dòng)機(jī)理論

第一章　基礎(chǔ)知識(shí)
　1.1　集合及其運(yùn)算
　1.2　關(guān)系
　　1.2.1　二元關(guān)系
　　1.2.2　等價(jià)關(guān)系
　　1.2.3　關(guān)系的合成
　1.3　證明和證明的方法
　　1.3.1　反證法
　　1.3.2　歸納法
　　1.3.3　遞歸的定義與歸納證明
　1.4　圖與樹
　1.5　語(yǔ)言
　1.6　常用術(shù)語(yǔ)
　1.7　形式語(yǔ)言與自動(dòng)機(jī)的發(fā)展
　習(xí)題一
第二章　形式語(yǔ)言
　2.1　例子語(yǔ)言
　2.2　文法和語(yǔ)言的關(guān)系
　2.3　Chomsky對(duì)文法的分類
　2.4　文法產(chǎn)生語(yǔ)言
　2.5　推導(dǎo)樹
　2.6　空串定理
　2.7　消除左遞歸
　　2.7.1　消除直接左遞歸
　　2.7.2　消除間接左遞歸
　2.8　上下文無(wú)關(guān)文法的另一種表示
　2.9　語(yǔ)言之間的運(yùn)算及運(yùn)算的封閉性
　　2.9.1　語(yǔ)言之間的基本運(yùn)算
　　2.9.2　語(yǔ)言之間的運(yùn)算的封閉性
　　2.9.3　語(yǔ)言之間的其他運(yùn)算
　2.10　正則表達(dá)式和正則集
　習(xí)題二
第三章　有限狀態(tài)自動(dòng)機(jī)
　3.1　有限狀態(tài)自動(dòng)機(jī)
　3.2　有限狀態(tài)自動(dòng)機(jī)識(shí)別的語(yǔ)言
　3.3　有限狀態(tài)自動(dòng)機(jī)識(shí)別語(yǔ)言的例子
　3.4　不確定的有限狀態(tài)自動(dòng)機(jī)
　　3.4.1　不確定的有限狀態(tài)自動(dòng)機(jī)
　　3.4.2　不確定的有限狀態(tài)自動(dòng)機(jī)的確定化
　3.5　帶有s動(dòng)作的有限狀態(tài)自動(dòng)機(jī)
　3.6　有限狀態(tài)自動(dòng)機(jī)的一些變形
　　3.6.1　雙向的有限狀態(tài)自動(dòng)機(jī)
　　3.6.2　帶有輸出的有限狀態(tài)自動(dòng)機(jī)
　3.7　有限狀態(tài)接收機(jī)的存儲(chǔ)技術(shù)
　習(xí)題三
第四章　正則語(yǔ)言
　4.1　正則語(yǔ)言與有限狀態(tài)自動(dòng)機(jī)
　　4.1.1　正則表達(dá)式對(duì)應(yīng)有限狀態(tài)自動(dòng)機(jī)
　　4.1.2　正則語(yǔ)言的等價(jià)模型
　4.2　正則語(yǔ)言的泵浦引理
　4.3　正則語(yǔ)言對(duì)運(yùn)算的封閉性
　4.4　正則語(yǔ)言類中的判定算法
　習(xí)題四
第五章　下推自動(dòng)機(jī)
　5.1　下推自動(dòng)機(jī)
　　5.1.1　確定的下推自動(dòng)機(jī)
　　5.1.2　不確定的下推自動(dòng)機(jī)
　　5.1.3　下推自動(dòng)機(jī)接收語(yǔ)言的兩種方式
　　5.1.4　廣義的下推自動(dòng)機(jī)和單態(tài)下推自動(dòng)機(jī)
　　5.1.5　下推自動(dòng)機(jī)的存儲(chǔ)技術(shù)
　　5.1.6　下推自動(dòng)機(jī)掃描多個(gè)符號(hào)
　5.2　上下文無(wú)關(guān)文法和范式
　　5.2.1　Chomsky范式
　　5.2.2　Greibach范式
　5.3　下推自動(dòng)機(jī)與上下文無(wú)關(guān)語(yǔ)言
　習(xí)題五
第六章　圖靈機(jī)
參考文獻(xiàn)