形式語言與自動機

第1章  基礎(chǔ)知識                  
 1. 1  集合與關(guān)系                  
 1. 2  邏輯                  
 1. 3  圖                  
 1. 4  證明技術(shù)                  
 1, 4. 1  演繹證明                  
 1. 4. 2  反證法                  
 1. 4. 3  歸納定義與歸納法                  
 習題                  
                   
 第2章  語言及文法                  
 2. 1  語言的定義與運算                  
 2. 2  文法                  
 2. 3  文法的分類                  
 習題                  
                   
 第3章  有限自動機和右線性文法                  
 3. 1  有限自動機                  
 3. 1. 1  有限狀態(tài)系統(tǒng)和有限自動機的概念                  
 3. 1. 2  有限自動機的形式定義                  
 3. 1. 3  設(shè)計有限自動機                  
 3. 2  不確定的有限自動機                  
 3. 3  DFA與NFA的等效                  
 3. 4  有c轉(zhuǎn)換的不確定的有限自動機                  
 3. 5  正則集與正則式                  
 3. 6  右線性文法和正則集                  
 3. 7  正則表達式和有限自動機                  
 3. 8  右線性語言與有限自動機                  
 3. 9  右線性語言的性質(zhì)                  
 3. 9. 1  確定的有限自動機的化簡                  
 3. 9. 2  泵浦引理                  
 3. 9. 3  右線性語言的封閉性                  
 3. 9. 4  判定問題                  
 3. 10  雙向和有輸出的有限自動機                  
 3. 10. 1  雙向有限自動機                  
 3. 10. 2  有輸出的有限自動機                  
 習題                  
                   
 第4章  上下文無關(guān)文法與下推自動機                  
 4. 1  推導(dǎo)樹與二義性                  
 4. 2  上下文無關(guān)文法的變換                  
 4. 3  Chomsky范式和Greibach范式                  
 4. 4  下推自動機                  
 4. 5  上下文無關(guān)文法與下推自動機                  
 4. 6  上下文無關(guān)語言的性質(zhì)                  
 4. 6. 1  關(guān)于上下文無關(guān)語言的泵浦引理                  
 4. 6. 2  上下文無關(guān)語言的封閉性                  
 4. 6. 3  上下文無關(guān)語言的判定問題                  
 4. 6. 4  二義性                  
 4. 7  受限型上下文無關(guān)文法                  
 習題                  
                   
 第5章  圖靈機                  
 5. 1  基本圖靈機                  
 5. 2  圖靈機的構(gòu)造技術(shù)                  
 5. 2. 1  控制器的存儲                  
 5. 2. 2  多道機                  
 5. 2. 3  核對符                  
 5. 2. 4  移位                  
 5. 2. 5  子程序                  
 5. 3  修改型圖靈機                  
 5. 3. 1  雙向無限帶圖靈機                  
 5. 3. 2  多帶圖靈機                  
 5. 3. 3  不確定的圖靈機                  
 5. 3. 4  二維圖靈機                  
 5. 4  圖靈機與無限制文法                  
 5. 5  線性有界自動機與上下文有關(guān)文法                  
 習題                  
                   
 第6章  翻譯                  
 6. 1  翻譯式                  
 6. 2  轉(zhuǎn)換器                  
 6. 2. 1有限轉(zhuǎn)換器                  
 6. 2. 2下推轉(zhuǎn)換器                  
 6. 3  詞法分析                  
 6. 4  句法分析                  
 6. 4. 1  自上而下解析                  
 6. 4. 2  自下而上解析                  
 習題                  
                   
 第7章  自動機理論在通信領(lǐng)域的應(yīng)用                  
 7. 1  狀態(tài)機基本模型及其局限性                  
 7. 2  MSC和SDL簡介                  
 7. 3  應(yīng)用狀態(tài)機模型描述協(xié)議                  
 附錄  計算復(fù)雜性與可計算性基礎(chǔ)                  
 參考文獻