形式語言與自動機理論因其以體現計算學科中模型描述、模型研究和模型計算為問題求解的主要特征而成為計算機科學與技術、軟件工程、網絡空間安全等計算機類學科教育的最重要的內容之一。本書按照我國當前計算機類及相關學科研究生教育實際需求，結合作者30余年的教學實踐編著而成，以正則語言與上下文無關語言的文法、識別模型及其性質，以及圖靈機基本知識為載體，分9章討論相關內容，力圖強化學生基於模型的建立、研究、處理，實現問題求解的意識，讓學生掌握相應的基本方法，提升解決問題的能力與水平。本書適合計算機類及相關學科研究生使用，也可以供相關專業高年級本科生、教師和科研人員參考。蔣宗禮，教授，博士生導師。國家級教學名師，享受政府特殊津貼，國家精品課程、國家精品資源共享課「編譯原理」負責人、計算機軟件基礎課國家級教學團隊負責人,主編高等教育「十一五」、「十二五」國家級規划教材多部，《形式語言與自動機理論》為普通高等教育國家級精品教材。獲國家教學成果二等獎2項，省部級教學、科研獎勵十多項。曾獲CCF傑出教育獎和中國高校優秀青年學者、寶鋼優秀教師、航天部優秀青年教師等榮譽稱號。主要學術兼職有中國工程教育認證協會學術委員會委員、結論審議委員會委員、計算機類專業認證委員會委員、教育部高校計算機類專業教學指導委員會副主任，歷任全國高校計算機教育研究會正、副理事長，中國計算機學會教育專委正、副主任，中國計算機學會教育工委正、副主任，是計算機類國家級教學團隊協作組發起人、國家精品資源共享課建設專家組成員。近年主講編譯原理、形式語言與自動機理論、新生研討課等。

第1章 語言與文法 1.1 語言 1.1.1 什麼是語言 1.1.2 形式語言與自動機理論的產生 1.1.3 基本概念 1.2 文法 1.3 文法的構造 1.4 文法的喬姆斯基體系 1.5 空語句 1.6 小結 習題第2章 有窮狀態自動機 2.1 語言的識別 2.2 有窮狀態自動機 2.3 不確定的有窮狀態自動機 2.3.1 作為對DFA的修改 2.3.2 NFA的形式定義 2.3.3 NFA與DFA等價 2.4 帶空移動的有窮狀態自動機 2.5 FA是正則語言的識別器 2.5.1 FA與右線性文法 2.5.2 FA與左線性文法 2.6 FA的一些變形 2.6.1 雙向有窮狀態自動機 2.6.2 帶輸出的 2.7 小結 習題第3章 正則表達式 3.1 啟示 3.2 正則表達式的形式定義 3.3 正則表達式與FA等價 3.3.1 正則表達式到FA的等價變換 3.3.2 正則語言可以用正則表達式表示 3.4 正則語言等價模型的總結 3.5 小結 習題第4章 正則語言的性質 4.1 正則語言的泵引理 4.2 正則語言的封閉性 4.3 Myhill-Nerode定理與DFA的極小化 4.3.1 Myhill-Nerode定理 4.3.2 DFA的極小化 4.4 關於正則語言的判定算法 4.5 小結 習題第5章 上下文無關語言 5.1 上下文無關文法 5.1.1 上下文無關文法的派生樹 5.1.2 二義性 5.1.3 自頂向下的分析和自底向上的分析 5.2 上下文無關文法的化簡 5.2.1 去無用符號 5.2.2 去ε-產生式 5.2.3 去單一產生式組 5.3 喬姆斯基范式 5.4 格雷巴赫范式 5.5 自嵌套文法 5.6 小結 習題第6章 下推自動機 6.1 基本定義 6.2 PDA與CFG等價 6.2.1 PDA用空棧接受和用終止狀態接受等價 6.2.2 PDA與CFG等價 6.3 小結 習題第7章 上下文無關語言的性質 7.1 上下文無關語言的泵引理 7.2 上下文無關語言的封閉性 7.3 上下文無關語言的判定算法 7.3.1 L空否的判定 7.3.2 L是否有窮的判定 7.3.3 x是否為L的句子的判定 7.4 小結 習題第8章 圖靈機 8.1 基本概念 8.1.1 基本圖靈機 8.1.2 圖靈機作為非負整函數的計算模型 8.1.3 圖靈機的構造 8.2 圖靈機的變形 8.2.1 雙向無窮帶圖靈機 8.2.2 多帶圖靈機 8.2.3 不確定的圖靈機 8.2.4 多維圖靈機 8.2.5 其他圖靈機 8.3 通用圖靈機 8.4 幾個相關的概念 8.4.1 可計算性 8.4.2 P與NP相關問題 8.5 小結 習題第9章 上下文有關語言 9.1 圖靈機與短語結構文法的等價性 9.2 線性有界自動機及其與上下文有關文法的等價性 9.3 小結 習題附錄縮寫符號詞匯索引參考文獻