編輯推薦

本書集作者30餘年相應課程的教學經驗和20餘年對專業教育的研究體會編著而成。自第1版在2003年齣版以來，受到讀者的厚愛，成為國內主創的、發行量大、優秀的形式語言與自動機理論教材。第1版獲北京市教學成果一等奬、北京市精品教材，第2版獲2008年度普通高等教育精品教材、北京市精品教材。
　　 本書作為《形式語言與自動機理論》一書的配套讀物，按照原書的結構編寫而成。重點討論有關內容的講解和學習的要點、問題分析、求解思路和方法、注意事項、典型習題的解析等。按照小節給齣知識點和主要內容解讀。為讀者學習和掌握原書中的知識點和問題求解方法、體會問題求解的核心思想提供幫助，對教師和學生來說，閱讀這些內容都是有意義的。
　　l 通過模型建立、等價變換、性質分析，使讀者逐漸熟悉模型計算。層次分明，循序漸進，符閤認知規律，突齣設計形態，很好地體現瞭本專業理工兼有的特徵和學科“抽象第1”的基本教育原理。
　　l 引導能力導嚮的教育。以知識為載體，注重模型建立、構造、變換、證明的方法與思想探討，挖掘知識背後的內容，強化專業基本能力和創新能力的培養。
　　l 取材閤適，結構嚴謹，深入淺齣，把握知識點間的聯係，安排鋪墊，分散難點，突齣重點，努力化解深奧，保持基本內容抽象和形式化，通過思路錶達的可視化提高瞭易懂性，富有啓發性，使抽象、枯燥的內容變得吸引人。
　　l 配有大量難度適當、前後呼應、富有啓發性、努力結閤專業、宏觀和微觀兼有的習題。主教材附教學設計、縮寫符號、詞匯索引等，便於學習。
　　教學資源：
　　l 《形式語言與自動機理論 (第3版)》（ISBN 9787302318026）：本書結閤作者30年講授形式語言與自動機理論的經驗，選擇和組織有關內容撰寫而成。全書分10章，介紹基礎知識，形式語言，文法，正則語言的文法、自動機、正則錶達式描述和性質，上下文無關語言的文法及下推自動機描述及其性質，圖靈機，上下文有關語言的綫性有界自動機描述等。本書的討論盡量追求問題求解的方法和思想，緻力於學生計算思維能力的培養。
　　l 主教材的PPT電子課件：可在清華大學齣版社網站下載。
　　 本書是學習“形式語言與自動機理論”課程的優秀的經典教材，配套教學資源豐富。本書的PPT電子課件、配套的源代碼，可在清華大學齣版社官網http://www.tup.com.cn下載。

內容簡介

　　《“十二五”普通高等教育本科國傢級規劃教材：形式語言與自動機理論教學參考書（第3版）》作為《形式語言與自動機理論（第3版）》（主教材）的配套教學輔導用書，按照主教材的結構編寫而成。《“十二五”普通高等教育本科國傢級規劃教材：形式語言與自動機理論教學參考書（第3版）》包括有關內容的講解、學習要點、問題分析、求解思路和方法、注意事項。考慮到該課程習題求解具有相當的難度，以及給齣全部習題解答又不利於學生學習，隻給齣瞭典型習題的解析。為瞭引導讀者及時總結學習內容，按照小節給齣知識點和主要內容解讀，為讀者學習和掌握主教材中的知識點和問題求解方法，體會問題求解的核心思想提供幫助，對教師和學生來說，閱讀這些內容都是很有意義的。

作者簡介

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

內頁插圖

目錄

第1章 緒論
1.1 集閤的基礎知識
1.1.1 集閤及其錶示
1.1.2 集閤之間的關係
1.1.3 集閤的運算
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.4.1 什麼是語言
1.4.2 形式語言與自動機理論的産生與作用
1.4.3 基本概念
1.5 小結
1.6 典型習題解析

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

第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 小結
3.8 典型習題解析

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

第5章 正則語言的性質
5.1 正則語言的泵引理
5.2 正則語言的封閉性
5.3 Myhill�睳erode定理與DFA的極小化
5.3.1 Myhill�睳erode定理
5.3.2 DFA的極小化
5.4 關於正則語言的判定算法
5.5 小結
5.6 典型習題解析

第6章 上下文無關語言
6.1 上下文無關文法
6.1.1 上下文無關文法的派生樹
6.1.2 二義性
6.1.3 自頂嚮下的分析和自底嚮上的分析
6.2 上下文無關文法的化簡
6.2.1 去無用符號
6.2.2 去ε�膊�生式
6.2.3 去單一産生式
6.3 喬姆斯基範式
6.4 格雷巴赫範式
6.5 自嵌套文法
6.6 小結
6.7 典型習題解析

第7章 下推自動機
7.1 基本定義
7.2 PDA與CFG等價
7.2.1 PDA用空棧接受和用終止狀態接受等價
7.2.2 PDA與CFG等價
7.3 小結
7.4 典型習題解析

第8章 上下文無關語言的性質
8.1 上下文無關語言的泵引理
8.2 上下文無關語言的封閉性
8.3 上下文無關語言的判定算法
8.3.1 L空否的判定
8.3.2 L是否有窮的判定
8.3.3 x是否為L的句子的判定
8.4 小結
8.5 典型習題解析

第9章 圖靈機
9.1 基本概念
9.1.1 基本圖靈機
9.1.2 圖靈機作為非負整函數的計算模型
9.1.3 圖靈機的構造
9.2 圖靈機的變形
9.2.1 雙嚮無窮帶圖靈機
9.2.2 多帶圖靈機
9.2.3 不確定的圖靈機
9.2.4 多維圖靈機
9.2.5 其他圖靈機
9.3 通用圖靈機
9.4 幾個相關的概念
9.4.1 可計算性
9.4.2 P與NP相關問題
9.5 小結
9.6 典型習題解析

第10章 上下文有關語言
10.1 圖靈機與短語結構文法的等價性
10.2 綫性有界自動機及其與上下文有關文法的等價性
10.3 小結
10.4 典型習題解析

第11章 內容歸納
11.1 文法與語言
11.2 正則語言
11.3 上下文無關語言
11.4 圖靈機

第12章 教學設計
12.1 概述
12.2 課程內容體係
12.2.1 課程的基本描述
12.2.2 教學定位
12.2.3 知識點與學時分配
12.3 講授提示
12.3.1 重點與難點
12.3.2 講授中應注意的方法等問題
12.4 習題與實驗
12.4.1 指導思想
12.4.2 關於大作業和實驗
12.5 考試與成績記載
12.5.1 成績評定
12.5.2 考題設計
參考文獻

前言/序言

　第3版前言FOREWORD培養創新人纔，對本科教育來講，主要是夯實基礎、訓練思維、養成探索之習慣。所以，創新能力（innovation ability）的培養不能著眼於眼前，簡單追求立竿見影，必須麵嚮未來，尋求可持續發展。所以，要追求雄厚的基礎(fundaments)、有效的思維（thinking）、勤奮的實踐（practice），這3點簡單歸納為“厚基礎、善思維、常實踐”，可以用如下公式錶示：I=F+T+P
首先是“厚基礎”，包括知識基礎和能力基礎。對計算機類專業人纔來說，重要的理論基礎主要來自於理論課程的學習。認真深入地讀幾本基礎性的書，深入理解其中的內容，使自己的思想水平上升到一個新的高度，是非常必要的。為瞭達到學習知識以提升能力的目的，就要在學習知識的同時，注重對其中蘊含的思想和方法的學習，培養主動探索意識與精神。其次是“善思維”。古人雲：“學而不思則罔，思而不學則殆。”要想將書中的知識轉化成自己的知識和能力，就必須在認真讀書的過程中勤奮地思考。在培養創新思維能力的過程中建立創新意識，形成創新能力。最後，“常實踐”是手段。在實踐中去加深理解，實踐探索。“動手能力”不能是狹義的，它不僅僅簡單地來自於下工廠、進企業、進實驗室的活動，更不是簡單地“編程序”。作為一名科技工作者，“動手”的關鍵在於“動腦”。
就計算學科而言，離開瞭理論的指導，就很難有高水平的實踐。作者認為，“理論，可以使人‘站到巨人的肩膀上’，並擁有一個‘智慧的腦’”；“實踐，需要用智慧的腦，練就一雙靈巧的手，去開創一個新世界”。不應該將理論和實踐教學割裂開，要有意識地將它們融在一起，這樣會收到事半功倍的效果。這就是說，既要“動手”又要“動腦”，要用高水平的動腦，去“指揮”高水平的動手，也就是“理性實踐”。而且，不同的專業、不同的課程需要不同形式的實踐。就本課程而言，認真地讀書，思考一些問題，做一些各種難度的練習，就是一種常規的實踐。在這個過程中領悟大師們的思維，從而達到訓練思維、提升思維水平的目的，不斷強化自己探索未知的意識，提升探索的能力。
這些能力導嚮教育的思想如何體現在教材中？如何引導讀者去發現問題、分析問題、解決問題？如何使得這些引導既深入又簡單？它們一直是作者努力探討的問題。在本書的寫作中，除瞭敘述基本的知識內容外，還努力進行著問題的分析，從而使這些分析在本書中占有很大的篇幅。建議讀者不要簡單地背定義、定理，要深入地理解，達到能夠用自己的語言錶達它們的程度。特彆要注意認真地閱讀分析部分，其中的某一句話可能會使讀者産生“恍然大悟”之感，而某一句話可能會引導讀者思考更深入的問題。希望讀者能夠仔細地閱讀這些內容，相信會有更多的收獲。
本套書自2003年1月齣版以來，其第1版在2004年獲北京市高等教育教學成果一等奬，2005年被評為北京市精品教材。該套書的第2版是普通高等教育“十一五”國傢級規劃教材，2008年被評為國傢級普通高等教育精品教材。本版作為普通高等教育“十二五”國傢級規劃教材齣版。作者看到，10年來，該教材一直受到讀者的歡迎和鼓勵，開設此課程的學校很多將其選為教材，使得該套教材成為國內同類教材中發行量和影響力最大的精品教材。另外，清華大學齣版社對本套教材的建設，給予瞭很大的支持，特彆是本書的責任編輯張瑞慶編審發揮瞭重要作用。在此，我們一並錶示真誠的感謝。我們相信，隨著計算機專業教育的發展，在大傢的支持下，該課程在高水平人纔的培養中將會進一步發揮作用。
對書中的錯誤，請讀者不吝賜教。
作者2013年2月

真是好動西真是好動西真是好動西

包裝很好 送貨神速。

不錯不錯。。

專業好書，等看完再評論。