有限自動機理論

《有限自動機理論》簡述了形式語言的基本內容，包括文法的分類和語言間運算的封閉性，有限自動機（包括有限狀態自動機、下推自動機和圖靈機）的基礎理論，從構造文法產生語言的角度和構造自動機識別語言的角度對語言進行討論，並介紹文法與自動機之間等價的轉換方法。

《有限自動機理論》除了在計算機科學與技術領域的直接應用外，更在計算機科學與技術領域的人才的計算思維的培養中佔有極其重要的地位。

《有限自動機理論》可作為高等學校計算機科學應用專業、軟體專業研究生的教材或參考書，也可作為計算機應用領域內廣大科技人員提高理論素質的參考書。

第一章　基礎知識

1.1　集合及其運算

1.2　關係

1.2.1　二元關係

1.2.2　等價關係

1.2.3　關係的合成

1.3　證明和證明的方法

1.3.1　反證法

1.3.2　歸納法

1.3.3　遞歸的定義與歸納證明

1.4　圖與樹

1.5　語言

1.6　常用術語

1.7　形式語言與自動機的發展

習題一

第二章　形式語言

2.1　例子語言

2.2　文法和語言的關係

2.3　Chomsky對文法的分類

2.4　文法產生語言

2.5　推導樹

2.6　空串定理

2.7　消除左遞歸

2.7.1　消除直接左遞歸

2.7.2　消除間接左遞歸

2.8　上下文無關文法的另一種表示

2.9　語言之間的運算及運算的封閉性

2.9.1　語言之間的基本運算

2.9.2　語言之間的運算的封閉性

2.9.3　語言之間的其他運算

2.10　正則表達式和正則集

習題二

第三章　有限狀態自動機

3.1　有限狀態自動機

3.2　有限狀態自動機識別的語言

3.3　有限狀態自動機識別語言的例子

3.4　不確定的有限狀態自動機

3.4.1　不確定的有限狀態自動機

3.4.2　不確定的有限狀態自動機的確定化

3.5　帶有s動作的有限狀態自動機

3.6　有限狀態自動機的一些變形

3.6.1　雙向的有限狀態自動機

3.6.2　帶有輸出的有限狀態自動機

3.7　有限狀態接收機的存儲技術

習題三

第四章　正則語言

4.1　正則語言與有限狀態自動機

4.1.1　正則表達式對應有限狀態自動機

4.1.2　正則語言的等價模型

4.2　正則語言的泵浦引理

4.3　正則語言對運算的封閉性

4.4　正則語言類中的判定演演算法

習題四

第五章　下推自動機

5.1　下推自動機

5.1.1　確定的下推自動機

5.1.2　不確定的下推自動機

5.1.3　下推自動機接收語言的兩種方式

5.1.4　廣義的下推自動機和單態下推自動機

5.1.5　下推自動機的存儲技術

5.1.6　下推自動機掃描多個符號

5.2　上下文無關文法和範式

5.2.1　Chomsky範式

5.2.2　Greibach範式

5.3　下推自動機與上下文無關語言

習題五

第六章　圖靈機

參考文獻