形式語言與自動機理論因其以體現計算學科中模型描述、模型研究和模型計算為問題求解的主要特征而成為計算機科學與技術、軟件工程、網絡空間安全等計算機類學科教育的*重要的內容之一。本書按照我國當前計算機類及相關學科研究生教育實際需求，結合作者30余年的教學實踐編著而成，以正則語言與上下文無關語言的文法、識別模型及其性質，以及圖靈機基本知識為載體，分9章討論相關內容，力圖強化學生基于模型的建立、研究、處理，實現問題求解的意識，讓學生掌握相應的基本方法，提升解決問題的能力與水平。
本書適合計算機類及相關學科研究生使用，也可以供相關專業高年級本科生、教師和科研人員參考。
編輯推薦：形式語言與自動機理論因其以體現計算學科中模型描述、模型研究和模型計算為問題求解的主要特征而成為計算機科學與技術、軟件工程、網絡空間安全等計算機類學科教育的*重要內容之一。本書按照我國相關學科研究生教育當前的實際需求，根據作者30余年的教學實踐編著而成，以正則語言與上下文無關語言的文法、識別模型及其性質，以及圖靈機基本知識為載體，分9章討論相關內容，力圖使學生建立基于模型的建立、研究、處理而實現問題求解的意識，掌握相應的基本方法，提升解決問題的能力與水平。? 本書是基于國家精品教材《形式語言與自動機理論》編著的，重點考慮了研究生教育的需求。? 通過模型建立、等價變換、性質分析，使讀者逐漸熟悉模型計算。層次分明，循序漸進，符合認知規律，突出設計形態內容，很好地體現了本專業理工兼有的特征和學科抽象*的教育基本原理。? 引導能力導向的教育。以知識為載體，注重模型建立、構造、變換、證明的方法與思想探討，挖掘知識背后的內容，支持研究型教學，強化專業基本能力和創新能力的培養。? 取材合適，結構嚴謹，深入淺出，把握知識點間的聯系，安排鋪墊，分散難點，突出重點，努力化解深奧，保持基本內容抽象和形式化，通過思路表達的可視化提高了易懂性，富有啟發性，使抽象、枯燥的內容變得吸引人。? 配有大量難度適當、前后呼應、富有啟發性、努力結合專業、宏觀和微觀兼有的習題。附教學設計、縮寫符號、詞匯索引等，便于學習。教學資源：? 《形式語言與自動機理論(第3版)》（ISBN 9787302318026）：十二五普通高等教育本科*規劃教材，高等教育*精品教材，北京市教學成果一等獎，北京市高等教育精品教材。優秀經典教材。本書集作者30余年相應課程的教學經驗和20余年對專業教育的研究體會編著而成。自第1版在2003年出版以來，受到讀者的厚愛，成為是國內主創的、發行量*、*秀的形式語言與自動機理論教材。? 《形式語言與自動機理論教學參考書(第3版)》（ISBN 9787302317814）：本書根據作者作為《形式語言與自動機理論》一書的配套讀物，按照原書的結構編寫而成。重點討論有關內容的講解和學習的要點、問題分析、求解思路和方法、注意事項、典型習題的解析等。按照小節給出知識點和主要內容解讀。為讀者學習和掌握原書中的知識點和問題求解方法、體會問題求解的核心思想提供幫助，對教師和學生來說，閱讀這些內容都是有意義的。? 主教材的PPT電子課件：可在清華大學出版社網站下載。 本書是研究生和高年級本科生學習形式語言與自動機理論課程的優秀教材，配套教學資源豐富。本書的PPT電子課件、配套的源代碼，可在清華大學出版社官網http://www.tup.com.cn下載。
前言FOREWORD
計算機科學與技術、軟件工程、網絡空間安全等計算機類學科，統稱為計算學科。學科通過在計算機上建立模型和系統，模擬實際過程進行科學調查和研究；通過數據搜集、存儲、傳輸與處理等進行問題求解，包括科學、工程、技術和應用4部分。其科學部分的核心在于通過抽象建立模型實現對計算規律的研究；其工程部分的核心在于根據規律低成本地構建從基本計算系統到大規模復雜計算應用系統的各類系統；其技術部分的核心在于研究和發明用計算進行科學調查和研究中使用的基本手段和方法；其應用部分在于構建、維護和使用計算系統實現特定問題的求解。其根本問題是什么能且如何被有效地自動計算，而計算的自動化，均以問題描述和處理的符號化為基礎。從事計算機科學研究、工程設計、開發、運行、應用、維護的計算機人才都不例外。也正因為如此，才有人用問題抽象、系統抽象、數據抽象來表述對計算機類專業人才的基本要求。2016年6月2日，在吉隆坡召開的國際工程聯盟大會上，中國獲全票通過，正式加入《華盛頓協議》，成為第18個正式成員，這被認為是中國高等教育取得的具有里程碑意義的歷史性突破。該協議雖然是針對本科教育的，但對我們按照工程教育的要求，不斷提升研究生教育的水平與質量也是很重要的。根據《華盛頓協議》，工程被定義為包括數學、自然科學和工程知識、技術和技能整體的、有目的性的應用。可見，工程對基礎的強調。另外，《華盛頓協議》還規定，兩年制的專科教育旨在培養學生解決狹義工程問題的能力，三年制專科旨在培養學生解決廣義工程問題的能力，本科教育則聚焦培養學生解決復雜工程問題的能力。所謂的復雜工程問題是滿足如下條件的工程問題:(1) 必須運用深入的工程原理經過分析才可能解決；(2) 需求涉及多方面的技術、工程和其他因素，并可能相互有一定沖突；(3) 需要通過建立合適的抽象模型才能解決，在建模過程中需要體現出創造性；(4) 不是僅靠常用方法就可以完全解決的；(5) 問題中涉及的因素可能沒有完全包含在專業標準和規范中；(6) 問題相關各方利益不完全一致；(7) 具有較高的綜合性，包含多個相互關聯的子問題。作為本科教育后繼的研究生教育，顯然應該在本科教育的基礎上開展。但是目前存在的問題是，很多年來，由于各方面的限制，部分專業點的教育還很難說達到了這一基本定位的要求，表現出來的現象是，進入研究生階段學習的學生在對深入原理的掌握、分析方法的掌握，從而具有分析能力以及建立合適的抽象模型并且在建模過程中需要體現出創造性等方面都存在一定的差距。建模能力是如此之重要，以至于《華盛頓協議》還明確要求包括機械、電子、化工、建筑等在內的所有工科專業的教育都要包括數學、數值分析、統計，以及計算機和信息科學關于形式化方面的基本內容，以支持學科問題的分析和建模（WK2: (mathematics and computer)conceptuallybased mathematics, numerical analysis, statistics and formal aspects of computer and information science to support analysis and modeling applicable to the discipline）。作為培養工程應用型人才為主的計算機類學科專業，更應如此。而形式語言與自動機理論則是培養學生這些方面能力的非常恰當的重要載體。希望通過這類課程的教育，支持這一要求的達成，同時促進學生在基礎理論上更好地達到我國學位條例中 在本門學科上掌握堅實的基礎理論和系統的專門知識的要求。另外，從復雜工程問題的定義不難看出，解決這類問題，需要有扎實的基礎理論和深入的原理性知識，同時要強調對基本理論的應用。所以，包括研究生教育在內，需要追求理論指導下的、非簡單的、高水平實踐能力的培養，以追求高水平動腦指揮下的問題求解（實踐、動手）。落實到本教材對應的課程教育，絕不僅僅是要讓學生掌握其基本知識，而是要以這些知識為載體，使學生掌握其中的思想和典型方法，培養他們模型描述和模型計算的意識和能力。為此，要開展研究型的教與學: 教師在對問題的研究中教，學生在對未知的研究中學，努力體現基于產出（outcomebased education，OBE）的基本教育觀點，糾正基于課程的教育觀點（curricularbased education，CBE）。為了達到這一目的，在本書的寫作中，我們除了以定義、定理、算法的形式敘述基本概念和結論外，還盡力進行相關的問題分析。希望讀者不要限于簡單地記憶定義、定理和相應的算法，要通過深入的分析，掌握相關的知識、思想和方法。多提問題，多想問題，這樣才能有真正的收獲。本書是基于國家精品教材《形式語言與自動機》編著的，重點考慮了研究生教育的需求，全書共分9章。第1章介紹語言和文法，包括相關的基本概念、文法的構造、Chomsky體系、左線性文法和右線性文法。第2章討論有窮狀態自動機，包括有窮狀態自動機的定義、描述、構造方法，確定的、非確定的、帶空移動的有窮狀態自動機以及與正則文法的等價性。第3章研究正則表達式及其與有窮狀態自動機的等價性。第4章討論正則語言的性質，包括正則語言的泵引理、封閉性、MyhillNerode定理、極小化、判定算法。第5章為上下文無關語言，包括文法二義性、派生樹、化簡、Chomsky范式和Greibach范式。第6章討論下推自動機，包括基本定義和構造方法以及下推自動機與上下文無關文法的等價性。第7章是上下文無關語言的性質，包括上下文無關語言的泵引理、Ogden引理、封閉性、判定算法。第8章介紹圖靈機，包括基本定義、接受的語言、構造技術、通用圖靈機、ChurchTuring論題、圖靈機的變形、可計算語言、不可判定性、PNP問題。第9章介紹上下文有關語言，包括圖靈機與短語結構文法的等價性，以及線性界限自動機的定義及與上下文有關語言的關系。書中難免存在不足，請讀者不吝賜教。聯系地址: jiangzl@bjut.edu.cn。
作者2017年1月
蔣宗禮，教授，博士生導師。*教學名師，享受政府特殊津貼，國家精品課程、國家精品資源共享課編譯原理負責人、計算機軟件基礎課*教學團隊負責人, 主編高等教育十一五、十二五*規劃教材多部，《形式語言與自動機理論》為普通高等教育*精品教材。獲國家教學成果二等獎2項，省部級教學、科研獎勵十多項。曾獲CCF杰出教育獎和中國高校優秀青年學者、寶鋼優秀教師、航天部優秀青年教師等榮譽稱號。主要學術兼職有中國工程教育認證協會學術委員會委員、結論審議委員會委員、計算機類專業認證委員會委員、教育部高校計算機類專業教學指導委員會副主任，歷任全國高校計算機教育研究會正、副理事長，中國計算機學會教育專委正、副主任，中國計算機學會教育工委正、副主任，是計算機類*教學團隊協作組發起人、國家精品資源共享課建設專家組成員。近年主講編譯原理、形式語言與自動機理論、新生研討課等。
目錄CONTENTS
第1章語言與文法1
1.1語言2
1.1.1什么是語言2
1.1.2形式語言與自動機理論的產生2
1.1.3基本概念3
1.2文法9
1.3文法的構造18
1.4文法的喬姆斯基體系26
1.5空語句36
1.6小結38
習題38
第2章有窮狀態自動機44
2.1語言的識別44
2.2有窮狀態自動機46
2.3不確定的有窮狀態自動機57
2.3.1作為對DFA的修改57
2.3.2NFA的形式定義58
2.3.3NFA與DFA等價60
2.4帶空移動的有窮狀態自動機64
2.5FA是正則語言的識別器68
2.5.1FA與右線性文法68
2.5.2FA與左線性文法72
2.6FA的一些變形73
2.6.1雙向有窮狀態自動機74
2.6.2帶輸出的FA75
2.7小結76
習題77
第3章正則表達式82
3.1啟示82
3.2正則表達式的形式定義83
3.3正則表達式與FA等價85
3.3.1正則表達式到FA的等價變換85
3.3.2正則語言可以用正則表達式表示93
3.4正則語言等價模型的總結98
3.5小結100
習題100
第4章正則語言的性質103
4.1正則語言的泵引理103
4.2正則語言的封閉性108
4.3MyhillNerode定理與DFA的極小化114
4.3.1MyhillNerode定理114
4.3.2DFA的極小化122
4.4關于正則語言的判定算法130
4.5小結131
習題132
目錄形式語言與自動機理論引論第5章上下文無關語言134
5.1上下文無關文法134
5.1.1上下文無關文法的派生樹135
5.1.2二義性140
5.1.3自頂向下的分析和自底向上的分析143
5.2上下文無關文法的化簡145
5.2.1去無用符號146
5.2.2去ε產生式149
5.2.3去單一產生式組152
5.3喬姆斯基范式155
5.4格雷巴赫范式158
5.5自嵌套文法163
5.6小結164
習題164
第6章下推自動機168
6.1基本定義168
6.2PDA與CFG等價174
6.2.1PDA用空棧接受和用終止狀態接受等價174
6.2.2PDA與CFG等價177
6.3小結186
習題186
第7章上下文無關語言的性質189
7.1上下文無關語言的泵引理189
7.2上下文無關語言的封閉性195
7.3上下文無關語言的判定算法200
7.3.1L空否的判定200
7.3.2L是否有窮的判定201
7.3.3x是否為L的句子的判定202
7.4小結204
習題204
第8章圖靈機205
8.1基本概念206
8.1.1基本圖靈機206
8.1.2圖靈機作為非負整函數的計算模型213
8.1.3圖靈機的構造215
8.2圖靈機的變形221
8.2.1雙向無窮帶圖靈機221
8.2.2多帶圖靈機224
8.2.3不確定的圖靈機226
8.2.4多維圖靈機227
8.2.5其他圖靈機229
8.3通用圖靈機231
8.4幾個相關的概念233
8.4.1可計算性233
8.4.2P與NP相關問題233
8.5小結234
習題234
第9章上下文有關語言237
9.1圖靈機與短語結構文法的等價性237
9.2線性有界自動機及其與上下文有關文法的等價性240
9.3小結241
習題241
附錄縮寫符號243
詞匯索引245
參考文獻251
新書資訊