相關商品
商品簡介
作者簡介
名人/編輯推薦
序
目次
商品簡介
本書由“電子科技大學‘十二五’規劃研究生教材建議基金”資助出版。本書簡述形式語言的基本內容，包括文法的分類和語言間運算的封閉性；系統地論述有限自動機：有限狀態自動機、下推自動機和圖靈機(包括量子圖靈機)的基礎理論；從構造文法產生語言的角度和構造自動機識別語言的角度對語言進行討論；介紹文法與等價的自動機之間的轉換方法；并介紹有限自動機的一些典型應用。本書以新的思維方式為讀者提供了一把鑰匙，主要培養讀者的獨立思考能力，使用符號化的系統描述程序設計語言或自然語言的語法結構的能力，以及構造自動機的能力。
作者簡介
陳文宇，電子科技大學教授，從事計算機教學20余年，中國計算機學會高級會員。教育部——Intel精品課程“編譯原理”負責人；四川省精品課程“匯編語言程序設計”負責人；四川省高等教育“質量工程”計算機科學與技術專業綜合改革“教學手段與方式改革”負責人；電子科技大學教育教學改革研究重點專項課程與教學資源建設的研究與實踐“程序設計基礎”負責人；電子科技大學211創新人才培養；電子科技大學“十二五”規劃教材建設項目（研究生）；電子科技大學“985”項目優秀教學團隊支持計劃（研究生）；2次獲得電子科技大學優秀主講教師（A級教師）稱號；3次獲青年教師教學優秀獎；2011年Google Faculty Award （Google獎教金）（全國15人）；2012年或電子科技大學教學成果一等獎2項；二等獎1項。
名人/編輯推薦
陳文宇、田玲、程偉、劉貴松編著的《有限自動機理論(第2版)》共分為7章。第1章回顧本書所需的基本數學知識；第2章是形式語言的基本內容，包括文法的定義、分類，文法的構造方法，以及語言之間的運算的封閉性的討論；第3章、第4章介紹有限狀態自動機的構造方法及其對應的正則語言的性質；第5章介紹下推自動機；第6章是對圖靈機的討論；第7章介紹量子圖靈機。
本書的目標是，力求使計算機科學與技術學科各個專業的研究生掌握各類有限自動機的模型、構造方法和技巧，培養計算思維能力。
本書基本覆蓋了形式語言的基本內容和有限自動機的主要內容，可以作為計算機科學與技術學科各專業研究生的教材。
本書的目標是，力求使計算機科學與技術學科各個專業的研究生掌握各類有限自動機的模型、構造方法和技巧，培養計算思維能力。
本書基本覆蓋了形式語言的基本內容和有限自動機的主要內容，可以作為計算機科學與技術學科各專業研究生的教材。
序
前 言
本書由“電子科技大學‘十二五’規劃研究生教材建議基金”資助出版。
形式語言和自動機的理論是計算機科學的理論基礎。這些理論來源于：
(1) Chomsky對自然語言的研究。
(2) Backus和Naur使用BNF(巴科斯－諾爾范式)對ALGOL-60語言的語法規則的描述方式。
(3) Turing、Kleene、Neumann、Huffman等對自動機模型的研究。
形式語言和自動機理論的應用范圍已被擴展到生物工程、自動控制系統、圖像處理與模式識別等許多領域。
形式語言與與自動機理論包括3方面的內容：形式語言理論、自動機理論和形式語言與自動機等價性理論。本書主要討論自動機理論和形式語言與自動機等價性理論。
研究生的適應能力及創新能力在很大程度上取決于堅實的理論基礎和專業基礎知識，這是高質量研究生教育的重要特征之一。在當今計算機科學技術突飛猛進、專業知識日新月異的時代，只有扎實掌握專業的計算機理論基礎，才有可能在該專業從事科研、教學和其他技術工作，才能打好進行創造性研究的基礎。因此理論課程的學習就顯得尤為重要。研究生理論課程教學，必須立足于提高研究生的學術水平和科研能力，是實現研究生培養目標、保證研究生質量的重要環節。
全書共分為7章。第1章回顧本書所需的基本數學知識；第2章是形式語言的基本內容，包括文法的定義、分類，文法的構造方法，以及語言之間的運算的封閉性的討論；第3章、第4章介紹有限狀態自動機的構造方法及其對應的正則語言的性質；第5章介紹下推自動機；第6章是對圖靈機的討論；第7章介紹量子圖靈機。
本書的目標是，力求使計算機科學與技術學科各個專業的研究生掌握各類有限自動機的模型、構造方法和技巧，培養計算思維能力。
本書基本覆蓋了形式語言的基本內容和有限自動機的主要內容，可以作為計算機科學與技術學科各專業研究生的教材。
本書不注重定理的煩瑣證明過程，而強調問題的思考方法和思路的研究，以提高讀者的創新思維能力。
本書是在第1版的基礎上進行修訂的，增加了有限自動機的應用、量子圖靈機等內容。全書由陳文宇、田玲、程偉和劉貴松編著，龔天富教授審閱了全書。
感謝參考文獻的作者和翻譯人員。感謝電子工業出版社的王羽佳編輯為本書的出版所做的大量工作。本書在編寫過程中，還得到了李維順、郭凌立、朱建、袁野、曾紅和陳青然等人的熱情幫助，在此對他們及所有為本書的出版付出了辛勤勞動的同志表示衷心的感謝。
特別感謝北京工業大學的蔣宗禮教授，本書中借鑒了蔣宗禮教授的《形式語言與自動機理論(第2版)》的許多內容，且習題也來源于該書。
本書提供配套的課件，需要的讀者請登錄華信教育資源網注冊后免費下載。
由于編者水平有限，書中難免存在缺點和錯誤，殷切希望廣大讀者批評指正。
編著者
本書由“電子科技大學‘十二五’規劃研究生教材建議基金”資助出版。
形式語言和自動機的理論是計算機科學的理論基礎。這些理論來源于：
(1) Chomsky對自然語言的研究。
(2) Backus和Naur使用BNF(巴科斯－諾爾范式)對ALGOL-60語言的語法規則的描述方式。
(3) Turing、Kleene、Neumann、Huffman等對自動機模型的研究。
形式語言和自動機理論的應用范圍已被擴展到生物工程、自動控制系統、圖像處理與模式識別等許多領域。
形式語言與與自動機理論包括3方面的內容：形式語言理論、自動機理論和形式語言與自動機等價性理論。本書主要討論自動機理論和形式語言與自動機等價性理論。
研究生的適應能力及創新能力在很大程度上取決于堅實的理論基礎和專業基礎知識，這是高質量研究生教育的重要特征之一。在當今計算機科學技術突飛猛進、專業知識日新月異的時代，只有扎實掌握專業的計算機理論基礎，才有可能在該專業從事科研、教學和其他技術工作，才能打好進行創造性研究的基礎。因此理論課程的學習就顯得尤為重要。研究生理論課程教學，必須立足于提高研究生的學術水平和科研能力，是實現研究生培養目標、保證研究生質量的重要環節。
全書共分為7章。第1章回顧本書所需的基本數學知識；第2章是形式語言的基本內容，包括文法的定義、分類，文法的構造方法，以及語言之間的運算的封閉性的討論；第3章、第4章介紹有限狀態自動機的構造方法及其對應的正則語言的性質；第5章介紹下推自動機；第6章是對圖靈機的討論；第7章介紹量子圖靈機。
本書的目標是，力求使計算機科學與技術學科各個專業的研究生掌握各類有限自動機的模型、構造方法和技巧，培養計算思維能力。
本書基本覆蓋了形式語言的基本內容和有限自動機的主要內容，可以作為計算機科學與技術學科各專業研究生的教材。
本書不注重定理的煩瑣證明過程，而強調問題的思考方法和思路的研究，以提高讀者的創新思維能力。
本書是在第1版的基礎上進行修訂的，增加了有限自動機的應用、量子圖靈機等內容。全書由陳文宇、田玲、程偉和劉貴松編著，龔天富教授審閱了全書。
感謝參考文獻的作者和翻譯人員。感謝電子工業出版社的王羽佳編輯為本書的出版所做的大量工作。本書在編寫過程中，還得到了李維順、郭凌立、朱建、袁野、曾紅和陳青然等人的熱情幫助，在此對他們及所有為本書的出版付出了辛勤勞動的同志表示衷心的感謝。
特別感謝北京工業大學的蔣宗禮教授，本書中借鑒了蔣宗禮教授的《形式語言與自動機理論(第2版)》的許多內容，且習題也來源于該書。
本書提供配套的課件，需要的讀者請登錄華信教育資源網注冊后免費下載。
由于編者水平有限，書中難免存在缺點和錯誤，殷切希望廣大讀者批評指正。
編著者
目次
目 錄
第1章 基礎知識 1
1.1 集合及其運算 2
1.2 關系 4
1.2.1 二元關系 4
1.2.2 等價關系 5
1.2.3 關系的合成 5
1.3 證明和證明的方法 7
1.3.1 反證法 7
1.3.2 歸納法 8
1.3.3 遞歸的定義與歸納證明 8
1.4 圖與樹 9
1.5 語言 10
1.6 常用術語 10
1.7 形式語言與自動機的發展 12
習題1 14
第2章 形式語言簡介 15
2.1 例子語言 15
2.2 文法和語言的關系 20
2.2.1 文法 20
2.2.2 語言 22
2.2.3 文法和語言的3類問題 23
2.3 Chomsky對文法和語言的分類 24
2.4 文法產生語言 29
2.5 無用非終結符 37
2.6 推導樹 38
2.7 空串定理 40
2.8 消除左遞歸 41
2.8.1 消除直接左遞歸 41
2.8.2 消除間接左遞歸 42
2.9 上下文無關文法的另一種表示 44
2.10 語言之間的運算及運算的封閉性 45
2.10.1 語言之間的基本運算 45
2.10.2 語言之間的運算的封閉性 46
2.10.3 語言之間的其他運算 51
2.11 正則表達式和正則集 53
習題2 56
第3章 有限狀態自動機 58
3.1 有限狀態自動機 58
3.2 確定的有限狀態自動機接收的語言 60
3.3 確定的有限狀態自動機接收語言的例子 65
3.4 不確定的有限狀態自動機 77
3.4.1 不確定的有限狀態自動機的概念 77
3.4.2 不確定的有限狀態自動機的確定化 79
3.5 帶有 動作的有限狀態自動機 84
3.6 有限狀態自動機的一些變形 91
3.6.1 雙向的有限狀態自動機 91
3.6.2 帶有輸出的有限狀態自動機 92
3.7 有限狀態接收機的存儲技術 95
3.8 有限狀態自動機應用實例 97
習題3 103
第4章 正則語言 105
4.1 正則語言與有限狀態自動機 105
4.1.1 正則表達式對應有限狀態自動機 105
4.1.2 正則語言的等價模型 115
4.2 正則語言的泵浦引理 117
4.3 正則語言類中的判定算法 124
習題4 125
第5章 下推自動機 127
5.1 下推自動機 127
5.1.1 確定的下推自動機 128
5.1.2 不確定的下推自動機 131
5.1.3 下推自動機接收語言的兩種方式 133
5.1.4 廣義下推自動機和單態下推自動機 137
5.2 上下文無關文法和范式 139
5.2.1 Chomsky范式 140
5.2.2 Greibach范式 141
5.3 下推自動機與上下文無關語言 143
5.4 下推自動機應用實例 155
習題5 157
第6章 圖靈機 159
6.1 圖靈機的基本模型 159
6.1.1 圖靈機的定義 159
6.1.2 圖靈機的構造 162
6.2 圖靈機作為非負整數函數計算模型 167
6.3 圖靈機的構造技術 170
6.3.1 圖靈機的存儲技術 171
6.3.2 圖靈機的移動技術 174
6.3.3 圖靈機掃描多個符號技術 176
6.3.4 圖靈機的多道技術 187
6.3.5 圖靈機的查訖技術 191
6.3.6 圖靈機的子程序技術 192
6.4 圖靈機變形 195
6.4.1 雙向無窮帶圖靈機 195
6.4.2 多帶多讀/寫頭圖靈機 198
6.4.3 不確定圖靈機 200
6.4.4 多維圖靈機 202
6.4.5 其他圖靈機 202
6.5 通用圖靈機 205
6.5.1 編碼的目的 205
6.5.2 編碼方法 206
6.5.3 總結 208
6.6 圖靈機與短語結構語言 209
6.7 線性有界的圖靈機與上下文相關語言 209
6.8 圖靈機應用實例 209
習題6 214
第7章 量子自動機 216
7.1 量子有限自動機 219
7.1.1 Moore ＆ Crutchfield量子有限自動機的定義 219
7.1.2 Moore ＆ Crutchfield量子有限自動機所識別的語言 220
7.1.3 Moore ＆ Crutchfield量子正規語言的性質 221
7.1.4 Kondacs ＆ Watrous量子有限自動機的定義 221
7.1.5 Kondacs ＆ Watrous量子有限自動機的例子 223
7.1.6 量子有限自動機模型的研究進展概述 224
7.2 量子下推自動機 226
7.2.1 Moore ＆ Crutchfield量子下推自動機的定義 226
7.2.2 Moore ＆ Crutchfield量子文法的定義 226
7.2.3 Moore ＆ Crutchfield量子下推自動機所識別的語言 227
7.2.4 Moore ＆ Crutchfield量子下推自動機所識別的語言的代數性質 227
7.2.5 其他類型的量子下推自動機 228
7.2.6 量子下推自動機模型的研究進展概述 231
7.3 量子圖靈機 232
7.3.1 量子圖靈機的提出 232
7.3.2 Church-Turing-Deutsch原理 232
7.3.3 Bernstein ＆ Vazirani量子圖靈機 233
7.3.4 量子圖靈機模型與量子電路模型的等價：Yao定理 234
7.3.5 Gudder量子圖靈機 234
7.3.6 量子圖靈機模型的研究進展概述 236
參考文獻 238
第1章 基礎知識 1
1.1 集合及其運算 2
1.2 關系 4
1.2.1 二元關系 4
1.2.2 等價關系 5
1.2.3 關系的合成 5
1.3 證明和證明的方法 7
1.3.1 反證法 7
1.3.2 歸納法 8
1.3.3 遞歸的定義與歸納證明 8
1.4 圖與樹 9
1.5 語言 10
1.6 常用術語 10
1.7 形式語言與自動機的發展 12
習題1 14
第2章 形式語言簡介 15
2.1 例子語言 15
2.2 文法和語言的關系 20
2.2.1 文法 20
2.2.2 語言 22
2.2.3 文法和語言的3類問題 23
2.3 Chomsky對文法和語言的分類 24
2.4 文法產生語言 29
2.5 無用非終結符 37
2.6 推導樹 38
2.7 空串定理 40
2.8 消除左遞歸 41
2.8.1 消除直接左遞歸 41
2.8.2 消除間接左遞歸 42
2.9 上下文無關文法的另一種表示 44
2.10 語言之間的運算及運算的封閉性 45
2.10.1 語言之間的基本運算 45
2.10.2 語言之間的運算的封閉性 46
2.10.3 語言之間的其他運算 51
2.11 正則表達式和正則集 53
習題2 56
第3章 有限狀態自動機 58
3.1 有限狀態自動機 58
3.2 確定的有限狀態自動機接收的語言 60
3.3 確定的有限狀態自動機接收語言的例子 65
3.4 不確定的有限狀態自動機 77
3.4.1 不確定的有限狀態自動機的概念 77
3.4.2 不確定的有限狀態自動機的確定化 79
3.5 帶有 動作的有限狀態自動機 84
3.6 有限狀態自動機的一些變形 91
3.6.1 雙向的有限狀態自動機 91
3.6.2 帶有輸出的有限狀態自動機 92
3.7 有限狀態接收機的存儲技術 95
3.8 有限狀態自動機應用實例 97
習題3 103
第4章 正則語言 105
4.1 正則語言與有限狀態自動機 105
4.1.1 正則表達式對應有限狀態自動機 105
4.1.2 正則語言的等價模型 115
4.2 正則語言的泵浦引理 117
4.3 正則語言類中的判定算法 124
習題4 125
第5章 下推自動機 127
5.1 下推自動機 127
5.1.1 確定的下推自動機 128
5.1.2 不確定的下推自動機 131
5.1.3 下推自動機接收語言的兩種方式 133
5.1.4 廣義下推自動機和單態下推自動機 137
5.2 上下文無關文法和范式 139
5.2.1 Chomsky范式 140
5.2.2 Greibach范式 141
5.3 下推自動機與上下文無關語言 143
5.4 下推自動機應用實例 155
習題5 157
第6章 圖靈機 159
6.1 圖靈機的基本模型 159
6.1.1 圖靈機的定義 159
6.1.2 圖靈機的構造 162
6.2 圖靈機作為非負整數函數計算模型 167
6.3 圖靈機的構造技術 170
6.3.1 圖靈機的存儲技術 171
6.3.2 圖靈機的移動技術 174
6.3.3 圖靈機掃描多個符號技術 176
6.3.4 圖靈機的多道技術 187
6.3.5 圖靈機的查訖技術 191
6.3.6 圖靈機的子程序技術 192
6.4 圖靈機變形 195
6.4.1 雙向無窮帶圖靈機 195
6.4.2 多帶多讀/寫頭圖靈機 198
6.4.3 不確定圖靈機 200
6.4.4 多維圖靈機 202
6.4.5 其他圖靈機 202
6.5 通用圖靈機 205
6.5.1 編碼的目的 205
6.5.2 編碼方法 206
6.5.3 總結 208
6.6 圖靈機與短語結構語言 209
6.7 線性有界的圖靈機與上下文相關語言 209
6.8 圖靈機應用實例 209
習題6 214
第7章 量子自動機 216
7.1 量子有限自動機 219
7.1.1 Moore ＆ Crutchfield量子有限自動機的定義 219
7.1.2 Moore ＆ Crutchfield量子有限自動機所識別的語言 220
7.1.3 Moore ＆ Crutchfield量子正規語言的性質 221
7.1.4 Kondacs ＆ Watrous量子有限自動機的定義 221
7.1.5 Kondacs ＆ Watrous量子有限自動機的例子 223
7.1.6 量子有限自動機模型的研究進展概述 224
7.2 量子下推自動機 226
7.2.1 Moore ＆ Crutchfield量子下推自動機的定義 226
7.2.2 Moore ＆ Crutchfield量子文法的定義 226
7.2.3 Moore ＆ Crutchfield量子下推自動機所識別的語言 227
7.2.4 Moore ＆ Crutchfield量子下推自動機所識別的語言的代數性質 227
7.2.5 其他類型的量子下推自動機 228
7.2.6 量子下推自動機模型的研究進展概述 231
7.3 量子圖靈機 232
7.3.1 量子圖靈機的提出 232
7.3.2 Church-Turing-Deutsch原理 232
7.3.3 Bernstein ＆ Vazirani量子圖靈機 233
7.3.4 量子圖靈機模型與量子電路模型的等價：Yao定理 234
7.3.5 Gudder量子圖靈機 234
7.3.6 量子圖靈機模型的研究進展概述 236
參考文獻 238
您曾經瀏覽過的商品
購物須知
大陸出版品因裝訂品質及貨運條件與台灣出版品落差甚大，除封面破損、內頁脫落等較嚴重的狀態，其餘商品將正常出貨。
特別提醒：部分書籍附贈之內容(如音頻mp3或影片dvd等)已無實體光碟提供，需以QR CODE 連結至當地網站註冊“並通過驗證程序”，方可下載使用。
無現貨庫存之簡體書，將向海外調貨：
海外有庫存之書籍，等候約45個工作天;
海外無庫存之書籍，平均作業時間約60個工作天，然不保證確定可調到貨，尚請見諒。
為了保護您的權益，「三民網路書店」提供會員七日商品鑑賞期(收到商品為起始日)。
若要辦理退貨，請在商品鑑賞期內寄回，且商品必須是全新狀態與完整包裝(商品、附件、發票、隨貨贈品等)否則恕不接受退貨。
優惠價：87
235
海外經銷商無庫存，到貨日平均30天至45天