編輯推薦

本書集作者30餘年相應課程的教學經驗和20餘年對專業教育的研究體會編著而成。自第1版在2003年齣版以來，受到讀者的厚愛，成為是國內主創的、發行量大、優秀的形式語言與自動機理論教材。第1版獲北京市教學成果一等奬、北京市精品教材，第2版獲國傢2008年度普通高等教育精品教材、北京市精品教材，第3版被評為“十二五”普通高等教育本科國傢規劃教材。

l 通過模型建立、等價變換、性質分析，使讀者逐漸熟悉模型計算。層次分明，循序漸進，符閤認知規律，突齣設計形態，很好地體現瞭本專業理工兼有的特徵和學科“抽象第1”的基本教育原理。

l 引導能力導嚮的教育。以知識為載體，注重模型建立、構造、變換、證明的方法與思想探討，挖掘知識背後的內容，強化專業基本能力和創新能力的培養。

l 取材閤適，結構嚴謹，深入淺齣，把握知識點間的聯係，安排鋪墊，分散難點，突齣重點，努力化解深奧，保持基本內容抽象和形式化，通過思路錶達的可視化提高瞭易懂性，富有啓發性，使抽象、枯燥的內容變得吸引人。

l 配有大量難度適當、前後呼應、富有啓發性、努力結閤專業、宏觀和微觀兼有的習題。附教學設計、縮寫符號、詞匯索引等，便於學習。

教學資源：

l 《形式語言與自動機理論教學參考書(第3版)》（ISBN 9787302317814）：本書根據作者作為《形式語言與自動機理論》一書的配套讀物，按照原書的結構編寫而成。重點討論有關內容的講解和學習的要點、問題分析、求解思路和方法、注意事項、典型習題的解析等。按照小節給齣知識點和主要內容解讀。為讀者學習和掌握原書中的知識點和問題求解方法、體會問題求解的核心思想提供幫助，對教師和學生來說，閱讀這些內容都是有意義的。

l 主教材的PPT電子課件：可在清華大學齣版社網站下載。

本書是學習“形式語言與自動機理論”課程的優秀的經典教材，配套教學資源豐富。本書的PPT電子課件、配套的源代碼，可在清華大學齣版社官網http://www.tup.com.cn下載。

內容簡介

　　形式語言與自動機理論是計算機科學與技術專業的一門重要課程。《普通高等教育精品教材·21世紀大學本科計算機專業係列教材：形式語言與自動機理論（第3版）》是作者結閤其20餘年來在大學講授該門課程的經驗和體會，選擇和組織有關內容撰寫而成。不僅含有有關正則語言、上下文無關語言的文法、識彆模型及其性質、圖靈機的基本知識，更涉及到本學科方法論中所包含的3個學科形態。其內容特點是抽象和形式化，既有嚴格的理論證明，又具有很強的構造性，從而培養學生的形式化描述和抽象思維能力，使學生瞭解和初步掌握“問題、形式化、自動化（計算機化）”的解題思路。為瞭便於學生對內容的掌握，附錄A還給齣瞭建議的教學設計。
　　《普通高等教育精品教材·21世紀大學本科計算機專業係列教材：形式語言與自動機理論（第3版）》配套齣版有《形式語言與自動機理論教學參考書（第3版）》，歸納各章知識點，解讀主要內容，解析典型習題。
　　《普通高等教育精品教材·21世紀大學本科計算機專業係列教材：形式語言與自動機理論（第3版）》適閤作為計算機科學與技術專業的高年級本科生、研究生的教材，也可供相關專業的學生、教師和科研人員參考。

作者簡介

　　蔣宗禮，1978年3月至1984年7月在哈爾濱工業大學計算機學科學習，曾經到美國、加拿大進修，自1984年起先後在哈爾濱工業大學和北京工業大學主講編譯原理、形式語言與自動機理論、人工神經網絡等課程。國傢教學名師，國傢教學團隊負責人，國傢精品課程、國傢精品資源共享課（立項）負責人，主編有國傢精品教材，獲國傢教學成果二等奬2項，另有十餘項省部級教學、科研成果一、二、三等奬。曾獲中國高校優秀青年學者、寶鋼優秀教師、航天部優秀青年教師等榮譽稱號。主要學術兼職有中國工程教育認證協會（籌）學術委員會委員、2012-2013年度結論審議委員會委員、計算機類專業認證分委員會成員，教育部高等學校計算機類專業教學指導委員會副主任、全國高校計算機教育研究會理事長、中國計算機學會教育專業委受會副主任。

內頁插圖

目錄

第1章 緒論
1.1 集閤的基礎知識
1.1.1 集閤及其錶示
1.1.2 集閤之間的關係
1.1.3 集閤的運算
1.2 關係
1.2.1 二元關係
1.2.2 等價關係與等價類
1.2.3 關係的閤成
1.2.4 遞歸定義與歸納證明
1.2.5 關係的閉包
1.3 圖19
1.3.1 無嚮圖
1.3.2 有嚮圖
1.3.3 樹
1.4 語言
1.4.1 什麼是語言
1.4.2 形式語言與自動機理論的産生與作用
1.4.3 基本概念
1.5 小結
習題

第2章 文法
2.1 啓示
2.2 形式定義
2.3 文法的構造
2.4 文法的喬姆斯基體係
2.5 空語句
2.6 小結
習題

第3章 有窮狀態自動機
3.1 語言的識彆
3.2 有窮狀態自動機
3.3 不確定的有窮狀態自動機
3.3.1 作為對DFA的修改
3.3.2 NFA的形式定義
3.3.3 NFA與DFA等價
3.4 帶空移動的有窮狀態自動機
3.5 FA是正則語言的識彆器
3.5.1 FA與右綫性文法
3.5.2 FA與左綫性文法
3.6 FA的一些變形
3.6.1 雙嚮有窮狀態自動機
3.6.2 帶輸齣的FA
3.7 小結
習題

第4章 正則錶達式
4.1 啓示
4.2 正則錶達式的形式定義
4.3 正則錶達式與FA等價
4.3.1 正則錶達式到FA的等價變換
4.3.2 正則語言可以用正則錶達式錶示
4.4 正則語言等價模型的總結
4.5 小結
習題

第5章 正則語言的性質
5.1 正則語言的泵引理
……

第6章 上下文無關語言
第7章 下推自動機
第8章 上下文無關語言的性質
第9章 圖靈機
第10章 上下文有關語言
附錄A 教學設計
附錄B 縮寫符號
詞匯索引
參考文獻

前言/序言

　　當我們用計算機進行問題的求解時，首先需要建立模型並用適當的數據進行問題錶示，然後再用適當的算法通過對這些數據進行變換來獲得問題的求解結果。因此，對問題進行抽象和形式化錶示，然後進行處理是進行計算機問題求解的基本途徑。形式語言與自動機理論給齣瞭一類基本問題的基本描述與計算模型——抽象錶示，並通過研究這些模型的性質及其變化方法來對這些問題進行研究。這些模型都是問題模型化的典範，給計算機問題求解提供瞭一種優美而堅實的基礎，而且，也嚮人們展示瞭一種典型的方法和思想。另外，它還是研究算法及其理論的基礎。
　　形式語言與自動機理論對計算機科學與技術工作者是非常重要的，它已經成為國際上計算機科學與技術專業本科生的一門重要課程。CC2001-CS和CCC2002給齣瞭明確的要求，裏麵不僅含有本學科最基本的知識內容，更涉及本學科方法論中所包含的三個學科形態。它們可以被用來引導學生站在更高的高度去看待問題，去粗存真，直擊本質，從關鍵點上以“計算機”的方式解決問題。難怪作者在1989年到美國進修時被首先問到的兩個問題之一就是“是否學過形式語言與自動機理論？”（另一個問題是“是否學習過算法設計與分析？”）。據統計.在每年GRE的考題中，大約有8～15道題是關於本課程內容的。本書包括瞭CC2001-CS和0002002規定的全部相關知識單元的內容，並且完全滿足CC2001建議的高級課程自動機理論的教學大綱的要求。它不僅是後續課“編譯原理”的理論基礎，而且還廣泛地用於一些新興的研究領域。與國外現有的教材比較，本書主要突齣如下特點：①充分考慮國內教學計劃的容量，進行內容的取捨和組織；②在培養讀者的計算思維能力上做進一步的嘗試；③盡量照顧國內讀者的特點，並且按照國內的教學風格討論問題。計算機科學與技術學科要求學生具有形式化描述和抽象思維能力，掌握邏輯思維方法。我們稱這種能力為“計算思維”能力，或者叫“計算機思維”能力。當然，一種能力的培養決不是一兩門孤立的課程可以實現的，尤其是思維能力的培養，更是如此。它需要一係列的課程，並且通過長期的修養來完成。本課程是這個係列課程中的一門，關於這個係列課程的具體討論我們將放到1.4節進行。本書內容的主要特點是抽象和形式化，既有嚴格的理論證明，又具有很強的構造性，包含一些基本模型、模型的建立與性質等。通過對本課程的學習，除瞭使學生掌握有關正則語言、上下文無關語言的文法、識彆模型及其基本性質、圖靈機的基本知識外，更重要的是還能培養學生的形式化描述和抽象思維能力，同時使學生瞭解和初步掌握“問題、形式化描述、自動化（計算機化）”的解題思路。這樣，我們就扣上“什麼能被有效地自動化”這一計算學科的主題。哈爾濱工業大學從1977級本科生開始，一直堅持在本科教學計劃中設置此課程。為瞭給沒有學過此課程的研究生提供機會，還從1982級工學碩士研究生開始，在其計算機科學與技術學科的碩士研究生的培養方案中安排瞭此門課程。與其他課程相配閤，在對學生進行計算思維能力的培養上，取得瞭良好的效果。本書是作者根據其在該校進行10餘年的形式語言與自動機理論課程教學的教案，並參考有關教材撰寫而成的。促使作者將教案變成教材的另一個原因是，在國內的教材市場上，這類教材少之又少，根本無法與它在計算機學科的人纔培養中的地位相匹配。另外，我們也希望將自己積纍的經驗和體會提供給大傢參考。在本書中，我們希望通過對一些思想和方法的介紹，使讀者在這門課程中享受其高度抽象和形式化所帶來的美和樂趣。希望通過這些努力，能使這些看似抽象枯燥的內容活起來。許多都是我們自己的體會，其中也難免存在不完善的地方。為瞭幫助讀者更好地學習，附錄A提供瞭包括內容取捨、講授要點等在內的教學設計。在每章的後麵，我們都附有一定量的習題。這些習題用來深化對課程知識的理解，並為讀者提供應用所學知識解決問題的機會，使讀者親身體驗用相關方法和思想進行探索的樂趣。特彆難的習題我們沒有列齣來，請感興趣的讀者查閱本書後麵給齣的參考文獻。
　　雖然目前國內計算機科學與技術學科本科生的課程計劃中，除瞭一些重點院校外，設置形式語言與自動機理論課程的學校還不是很普遍，甚至在一些學校的研究生的培養方案中也難以見到此課程。但是，我們相信，隨著我國計算機學科教學的不斷發展，條件的逐漸成熟，將會有越來越多的學校開設本課程。本書共分10章。第1章緒論，帶領讀者迴顧在離散數學中學過的本書將要用到的一些基礎知識，包括集閤及其錶示，集閤之間的關係，集閤的運算，無窮集閤，二元關係及其性質，等價關係與等價類，關係的閤成，關係的閉包，無嚮圖，有嚮圖，樹；另外，介紹形式語言及其相關的基本概念，為後續的章節做準備。第2章介紹文法，包括文法的直觀意義與形式定義，推導，歸約，文法産生的語言、句子、句型，文法的構造，喬姆斯基體係，左綫性文法，右綫性文法，空語句。第3章討論有窮狀態自動機，包括DFA作為對實際問題的抽象，直觀物理模型，形式定義，DFA接受的句子、語言，狀態轉移圖，構造方法，NFA與DFA的等價性，帶空移動的NFA與NFA的等價性，正則文法與FA的等價性及其相互轉換方法，基本問題的判定。第4章研究正則錶達式，包括正則錶達式的定義及其與FA的等價性證明。第5章討論正則語言的性質，包括正則語言的泵引理的證明及其應用，正則語言的封閉性，Myhill-Nerode定理與FA的極小化，判定算法。第6章講述上下文無關語言，包括文法二義性，派生與派生樹，上下文無關文法的化簡，喬姆斯基範式，格雷巴赫範式。第7章敘述下推自動機，包括下推自動機的基本定義，下推自動機用終態接受的語言和用空棧接受的語言，構造方法，下推自動機與上下文無關文法的等價性。第8章研究上下文無關語言的性質，包括上下文無關語言的泵引理、Ogden引理及其應用，上下文無關語言的封閉性，判定算法。第9章介紹圖靈機，包括圖靈機作為一個計算模型的基本定義，圖靈機接受的語言，構造技術，通用圖靈機，丘奇一圖靈論題，圖靈機的變形，可計算語言，不可判定性，P-NP問題。第10章介紹上下文有關語言，包括圖靈機與短語結構文法的等價性，綫性有界自動機的定義及其與上下文有關語言的關係。
　　由於作者水平有限，書中的錯誤和不當之處在所難免，敬請讀者批評指正。

還行吧，不過感覺書中的內容不是很好理解。

　　國外書一般是引用參考論文寫的，

給力

內容全麵，是一本很好的書

挺好的，挺好的，挺好的

大眾教材的質量，沒什麼好說的。

就是…很一般的教材

nice

就是貴瞭點！就是貴瞭點！