掃一掃
關(guān)注中圖網(wǎng)
官方微博
>
>
自動(dòng)機(jī)理論、語(yǔ)言和計(jì)算導(dǎo)論(原書(shū)第3版·典藏版)
包郵 自動(dòng)機(jī)理論、語(yǔ)言和計(jì)算導(dǎo)論(原書(shū)第3版·典藏版)
開(kāi)本：
16開(kāi)
頁(yè)數(shù)：
380
本類(lèi)榜單：計(jì)算機(jī)/網(wǎng)絡(luò)銷(xiāo)量榜
本類(lèi)五星書(shū)更多>
-
>
全國(guó)計(jì)算機(jī)等級(jí)考試最新真考題庫(kù)模擬考場(chǎng)及詳解·二級(jí)MSOffice高級(jí)應(yīng)用
-
>
決戰(zhàn)行測(cè)5000題(言語(yǔ)理解與表達(dá))
-
>
軟件性能測(cè)試.分析與調(diào)優(yōu)實(shí)踐之路
-
>
第一行代碼Android
-
>
JAVA持續(xù)交付
-
>
EXCEL最強(qiáng)教科書(shū)(完全版)(全彩印刷)
-
>
深度學(xué)習(xí)
中圖價(jià):¥80.9
加入購(gòu)物車(chē)
自動(dòng)機(jī)理論、語(yǔ)言和計(jì)算導(dǎo)論(原書(shū)第3版·典藏版) 版權(quán)信息
- ISBN：9787111704294
- 條形碼：9787111704294 ; 978-7-111-70429-4
- 裝幀：一般膠版紙
- 冊(cè)數(shù)：暫無(wú)
- 重量：暫無(wú)
- 所屬分類(lèi)：>
自動(dòng)機(jī)理論、語(yǔ)言和計(jì)算導(dǎo)論(原書(shū)第3版·典藏版) 內(nèi)容簡(jiǎn)介
本書(shū)是關(guān)于形式語(yǔ)言、自動(dòng)機(jī)理論和計(jì)算復(fù)雜性方面的經(jīng)典之作。書(shū)中涵蓋了有窮自動(dòng)機(jī)、正則表達(dá)式與語(yǔ)言、正則語(yǔ)言的性質(zhì)、上下文無(wú)關(guān)文法及上下文無(wú)關(guān)語(yǔ)言、下推自動(dòng)機(jī)、上下文無(wú)關(guān)語(yǔ)言的性質(zhì)、圖靈機(jī)、不可判定性以及難解問(wèn)題等內(nèi)容。本書(shū)在定義和證明中使用了很多細(xì)節(jié)和直觀說(shuō)明，使用圖來(lái)幫助闡明思想，并包含了大量的難度各異的示例和習(xí)題，以便讀者確認(rèn)和加深對(duì)內(nèi)容的理解。本書(shū)已被世界許多有名大學(xué)作為計(jì)算機(jī)理論課程的教材或教學(xué)參考書(shū)，適合作為高校計(jì)算機(jī)專(zhuān)業(yè)高年級(jí)本科生及研究生的教材，還可供從事理論計(jì)算工作的研究人員參考。<br>
自動(dòng)機(jī)理論、語(yǔ)言和計(jì)算導(dǎo)論(原書(shū)第3版·典藏版) 目錄
譯者序
前言
第1章 自動(dòng)機(jī)：方法與體驗(yàn) 1
1.1 為什么研究自動(dòng)機(jī)理論 1
1.1.1 有窮自動(dòng)機(jī)簡(jiǎn)介 1
1.1.2 結(jié)構(gòu)表示法 3
1.1.3 自動(dòng)機(jī)與復(fù)雜性 3
1.2 形式化證明簡(jiǎn)介 3
1.2.1 演繹證明 4
1.2.2 求助于定義 6
1.2.3 其他定理形式 7
1.2.4 表面上不是“如果-則”命題的
定理 9
1.3 其他的證明形式 9
1.3.1 證明集合等價(jià)性 9
1.3.2 逆否命題 10
1.3.3 反證法 12
1.3.4 反例 12
1.4 歸納證明 13
1.4.1 整數(shù)上的歸納法 13
1.4.2 更一般形式的整數(shù)歸納法 16
1.4.3 結(jié)構(gòu)歸納法 16
1.4.4 互歸納法 18
1.5 自動(dòng)機(jī)理論的中心概念 19
1.5.1 字母表 19
1.5.2 串 20
1.5.3 語(yǔ)言 21
1.5.4 問(wèn)題 21
1.6 小結(jié) 23
1.7 參考文獻(xiàn) 24
第2章 有窮自動(dòng)機(jī) 25
2.1 有窮自動(dòng)機(jī)的非形式化描述 25
2.1.1 基本規(guī)則 26
2.1.2 協(xié)議 26
2.1.3 允許自動(dòng)機(jī)忽略動(dòng)作 27
2.1.4 整個(gè)系統(tǒng)成為一個(gè)自動(dòng)機(jī) 29
2.1.5 用乘積自動(dòng)機(jī)驗(yàn)證協(xié)議 30
2.2 確定型有窮自動(dòng)機(jī) 30
2.2.1 確定型有窮自動(dòng)機(jī)的定義 31
2.2.2 DFA如何處理串 31
2.2.3 DFA的簡(jiǎn)化記號(hào) 32
2.2.4 把轉(zhuǎn)移函數(shù)擴(kuò)展到串 33
2.2.5 DFA的語(yǔ)言 35
2.2.6 習(xí)題 35
2.3 非確定型有窮自動(dòng)機(jī) 37
2.3.1 非確定型有窮自動(dòng)機(jī)的非形式化觀點(diǎn) 37
2.3.2 非確定型有窮自動(dòng)機(jī)的定義 38
2.3.3 擴(kuò)展轉(zhuǎn)移函數(shù) 39
2.3.4 NFA的語(yǔ)言 39
2.3.5 確定型有窮自動(dòng)機(jī)與非確定型有窮自動(dòng)機(jī)的等價(jià)性 40
2.3.6 子集構(gòu)造的壞情形 43
2.3.7 習(xí)題 45
2.4 應(yīng)用：文本搜索 46
2.4.1 在文本中查找串 46
2.4.2 文本搜索的非確定型有窮自動(dòng)機(jī) 46
2.4.3 識(shí)別關(guān)鍵字集合的DFA 47
2.4.4 習(xí)題 49
2.5 帶e 轉(zhuǎn)移的有窮自動(dòng)機(jī) 49
2.5.1 e 轉(zhuǎn)移的用途 49
2.5.2 e-NFA的形式化定義 50
2.5.3 e 閉包 51
2.5.4 e-NFA的擴(kuò)展轉(zhuǎn)移和語(yǔ)言 52
2.5.5 消除 e 轉(zhuǎn)移 53
2.5.6 習(xí)題 54
2.6 小結(jié) 55
2.7 參考文獻(xiàn) 55
第3章 正則表達(dá)式與正則語(yǔ)言 57
3.1 正則表達(dá)式 57
3.1.1 正則表達(dá)式運(yùn)算符 57
3.1.2 構(gòu)造正則表達(dá)式 59
3.1.3 正則表達(dá)式運(yùn)算符的優(yōu)先級(jí) 60
3.1.4 習(xí)題 61
3.2 有窮自動(dòng)機(jī)和正則表達(dá)式 61
3.2.1 從DFA到正則表達(dá)式 62
3.2.2 通過(guò)消除狀態(tài)把DFA轉(zhuǎn)化為正則表達(dá)式 65
3.2.3 把正則表達(dá)式轉(zhuǎn)化為自動(dòng)機(jī) 69
3.2.4 習(xí)題 72
3.3 正則表達(dá)式的應(yīng)用 73
3.3.1 UNIX中的正則表達(dá)式 73
3.3.2 詞法分析 74
3.3.3 查找文本中的模式 76
3.3.4 習(xí)題 77
3.4 正則表達(dá)式代數(shù)定律 77
3.4.1 結(jié)合律與交換律 78
3.4.2 單位元與零元 78
3.4.3 分配律 79
3.4.4 冪等律 79
3.4.5 與閉包有關(guān)的定律 79
3.4.6 發(fā)現(xiàn)正則表達(dá)式定律 80
3.4.7 檢驗(yàn)正則表達(dá)式代數(shù)定律 81
3.4.8 習(xí)題 82
3.5 小結(jié) 83
3.6 參考文獻(xiàn) 84
第4章 正則語(yǔ)言的性質(zhì) 85
4.1 證明語(yǔ)言的非正則性 85
4.1.1 正則語(yǔ)言的泵引理 85
4.1.2 泵引理的應(yīng)用 87
4.1.3 習(xí)題 88
4.2 正則語(yǔ)言的封閉性 89
4.2.1 正則語(yǔ)言在布爾運(yùn)算下的封閉性 89
4.2.2 反轉(zhuǎn) 93
4.2.3 同態(tài) 94
4.2.4 逆同態(tài) 96
4.2.5 習(xí)題 99
4.3 正則語(yǔ)言的判定性質(zhì) 102
4.3.1 在各種表示之間轉(zhuǎn)化 102
4.3.2 測(cè)試正則語(yǔ)言的空性 104
4.3.3 測(cè)試正則語(yǔ)言的成員性 104
4.3.4 習(xí)題 105
4.4 自動(dòng)機(jī)的等價(jià)性和*小化 105
4.4.1 測(cè)試狀態(tài)的等價(jià)性 105
4.4.2 測(cè)試正則語(yǔ)言的等價(jià)性 107
4.4.3 DFA*小化 108
4.4.4 為什么不能比*小DFA更小 110
4.4.5 習(xí)題 111
4.5 小結(jié) 112
4.6 參考文獻(xiàn) 112
第5章 上下文無(wú)關(guān)文法及上下文無(wú)關(guān)語(yǔ)言 115
5.1 上下文無(wú)關(guān)文法 115
5.1.1 一個(gè)非形式化的例子 115
5.1.2 上下文無(wú)關(guān)文法的定義 116
5.1.3 使用文法來(lái)推導(dǎo) 118
5.1.4 *左推導(dǎo)和*右推導(dǎo) 119
5.1.5 文法的語(yǔ)言 120
5.1.6 句型 121
5.1.7 習(xí)題 122
5.2 語(yǔ)法分析樹(shù) 124
5.2.1 構(gòu)造語(yǔ)法分析樹(shù) 124
5.2.2 語(yǔ)法分析樹(shù)的產(chǎn)生 125
5.2.3 推理、推導(dǎo)和語(yǔ)法分析樹(shù) 125
5.2.4 從推理到樹(shù) 126
5.2.5 從樹(shù)到推導(dǎo) 127
5.2.6 從推導(dǎo)到遞歸推理 129
5.2.7 習(xí)題 131
5.3 上下文無(wú)關(guān)文法的應(yīng)用 131
5.3.1 語(yǔ)法分析器 131
5.3.2 語(yǔ)法分析器生成器YACC 133
5.3.3 標(biāo)記語(yǔ)言 134
5.3.4 XML和文檔類(lèi)型定義 135
5.3.5 習(xí)題 140
5.4 文法和語(yǔ)言的歧義性 141
5.4.1 歧義文法 141
5.4.
前言
第1章 自動(dòng)機(jī)：方法與體驗(yàn) 1
1.1 為什么研究自動(dòng)機(jī)理論 1
1.1.1 有窮自動(dòng)機(jī)簡(jiǎn)介 1
1.1.2 結(jié)構(gòu)表示法 3
1.1.3 自動(dòng)機(jī)與復(fù)雜性 3
1.2 形式化證明簡(jiǎn)介 3
1.2.1 演繹證明 4
1.2.2 求助于定義 6
1.2.3 其他定理形式 7
1.2.4 表面上不是“如果-則”命題的
定理 9
1.3 其他的證明形式 9
1.3.1 證明集合等價(jià)性 9
1.3.2 逆否命題 10
1.3.3 反證法 12
1.3.4 反例 12
1.4 歸納證明 13
1.4.1 整數(shù)上的歸納法 13
1.4.2 更一般形式的整數(shù)歸納法 16
1.4.3 結(jié)構(gòu)歸納法 16
1.4.4 互歸納法 18
1.5 自動(dòng)機(jī)理論的中心概念 19
1.5.1 字母表 19
1.5.2 串 20
1.5.3 語(yǔ)言 21
1.5.4 問(wèn)題 21
1.6 小結(jié) 23
1.7 參考文獻(xiàn) 24
第2章 有窮自動(dòng)機(jī) 25
2.1 有窮自動(dòng)機(jī)的非形式化描述 25
2.1.1 基本規(guī)則 26
2.1.2 協(xié)議 26
2.1.3 允許自動(dòng)機(jī)忽略動(dòng)作 27
2.1.4 整個(gè)系統(tǒng)成為一個(gè)自動(dòng)機(jī) 29
2.1.5 用乘積自動(dòng)機(jī)驗(yàn)證協(xié)議 30
2.2 確定型有窮自動(dòng)機(jī) 30
2.2.1 確定型有窮自動(dòng)機(jī)的定義 31
2.2.2 DFA如何處理串 31
2.2.3 DFA的簡(jiǎn)化記號(hào) 32
2.2.4 把轉(zhuǎn)移函數(shù)擴(kuò)展到串 33
2.2.5 DFA的語(yǔ)言 35
2.2.6 習(xí)題 35
2.3 非確定型有窮自動(dòng)機(jī) 37
2.3.1 非確定型有窮自動(dòng)機(jī)的非形式化觀點(diǎn) 37
2.3.2 非確定型有窮自動(dòng)機(jī)的定義 38
2.3.3 擴(kuò)展轉(zhuǎn)移函數(shù) 39
2.3.4 NFA的語(yǔ)言 39
2.3.5 確定型有窮自動(dòng)機(jī)與非確定型有窮自動(dòng)機(jī)的等價(jià)性 40
2.3.6 子集構(gòu)造的壞情形 43
2.3.7 習(xí)題 45
2.4 應(yīng)用：文本搜索 46
2.4.1 在文本中查找串 46
2.4.2 文本搜索的非確定型有窮自動(dòng)機(jī) 46
2.4.3 識(shí)別關(guān)鍵字集合的DFA 47
2.4.4 習(xí)題 49
2.5 帶e 轉(zhuǎn)移的有窮自動(dòng)機(jī) 49
2.5.1 e 轉(zhuǎn)移的用途 49
2.5.2 e-NFA的形式化定義 50
2.5.3 e 閉包 51
2.5.4 e-NFA的擴(kuò)展轉(zhuǎn)移和語(yǔ)言 52
2.5.5 消除 e 轉(zhuǎn)移 53
2.5.6 習(xí)題 54
2.6 小結(jié) 55
2.7 參考文獻(xiàn) 55
第3章 正則表達(dá)式與正則語(yǔ)言 57
3.1 正則表達(dá)式 57
3.1.1 正則表達(dá)式運(yùn)算符 57
3.1.2 構(gòu)造正則表達(dá)式 59
3.1.3 正則表達(dá)式運(yùn)算符的優(yōu)先級(jí) 60
3.1.4 習(xí)題 61
3.2 有窮自動(dòng)機(jī)和正則表達(dá)式 61
3.2.1 從DFA到正則表達(dá)式 62
3.2.2 通過(guò)消除狀態(tài)把DFA轉(zhuǎn)化為正則表達(dá)式 65
3.2.3 把正則表達(dá)式轉(zhuǎn)化為自動(dòng)機(jī) 69
3.2.4 習(xí)題 72
3.3 正則表達(dá)式的應(yīng)用 73
3.3.1 UNIX中的正則表達(dá)式 73
3.3.2 詞法分析 74
3.3.3 查找文本中的模式 76
3.3.4 習(xí)題 77
3.4 正則表達(dá)式代數(shù)定律 77
3.4.1 結(jié)合律與交換律 78
3.4.2 單位元與零元 78
3.4.3 分配律 79
3.4.4 冪等律 79
3.4.5 與閉包有關(guān)的定律 79
3.4.6 發(fā)現(xiàn)正則表達(dá)式定律 80
3.4.7 檢驗(yàn)正則表達(dá)式代數(shù)定律 81
3.4.8 習(xí)題 82
3.5 小結(jié) 83
3.6 參考文獻(xiàn) 84
第4章 正則語(yǔ)言的性質(zhì) 85
4.1 證明語(yǔ)言的非正則性 85
4.1.1 正則語(yǔ)言的泵引理 85
4.1.2 泵引理的應(yīng)用 87
4.1.3 習(xí)題 88
4.2 正則語(yǔ)言的封閉性 89
4.2.1 正則語(yǔ)言在布爾運(yùn)算下的封閉性 89
4.2.2 反轉(zhuǎn) 93
4.2.3 同態(tài) 94
4.2.4 逆同態(tài) 96
4.2.5 習(xí)題 99
4.3 正則語(yǔ)言的判定性質(zhì) 102
4.3.1 在各種表示之間轉(zhuǎn)化 102
4.3.2 測(cè)試正則語(yǔ)言的空性 104
4.3.3 測(cè)試正則語(yǔ)言的成員性 104
4.3.4 習(xí)題 105
4.4 自動(dòng)機(jī)的等價(jià)性和*小化 105
4.4.1 測(cè)試狀態(tài)的等價(jià)性 105
4.4.2 測(cè)試正則語(yǔ)言的等價(jià)性 107
4.4.3 DFA*小化 108
4.4.4 為什么不能比*小DFA更小 110
4.4.5 習(xí)題 111
4.5 小結(jié) 112
4.6 參考文獻(xiàn) 112
第5章 上下文無(wú)關(guān)文法及上下文無(wú)關(guān)語(yǔ)言 115
5.1 上下文無(wú)關(guān)文法 115
5.1.1 一個(gè)非形式化的例子 115
5.1.2 上下文無(wú)關(guān)文法的定義 116
5.1.3 使用文法來(lái)推導(dǎo) 118
5.1.4 *左推導(dǎo)和*右推導(dǎo) 119
5.1.5 文法的語(yǔ)言 120
5.1.6 句型 121
5.1.7 習(xí)題 122
5.2 語(yǔ)法分析樹(shù) 124
5.2.1 構(gòu)造語(yǔ)法分析樹(shù) 124
5.2.2 語(yǔ)法分析樹(shù)的產(chǎn)生 125
5.2.3 推理、推導(dǎo)和語(yǔ)法分析樹(shù) 125
5.2.4 從推理到樹(shù) 126
5.2.5 從樹(shù)到推導(dǎo) 127
5.2.6 從推導(dǎo)到遞歸推理 129
5.2.7 習(xí)題 131
5.3 上下文無(wú)關(guān)文法的應(yīng)用 131
5.3.1 語(yǔ)法分析器 131
5.3.2 語(yǔ)法分析器生成器YACC 133
5.3.3 標(biāo)記語(yǔ)言 134
5.3.4 XML和文檔類(lèi)型定義 135
5.3.5 習(xí)題 140
5.4 文法和語(yǔ)言的歧義性 141
5.4.1 歧義文法 141
5.4.
展開(kāi)全部
自動(dòng)機(jī)理論、語(yǔ)言和計(jì)算導(dǎo)論(原書(shū)第3版·典藏版) 作者簡(jiǎn)介
約翰·E.霍普克羅夫特（John E. Hopcroft） 1986年圖靈獎(jiǎng)獲得者、美國(guó)國(guó)家工程院院士、美國(guó)國(guó)家科學(xué)院院士、美國(guó)國(guó)家藝術(shù)與科學(xué)院院士、中國(guó)科學(xué)院外籍院士、美國(guó)康奈爾大學(xué)教授。他的研究興趣集中在計(jì)算理論方面，尤其是算法分析、自動(dòng)機(jī)理論等。他和Jeffrey D. Ullman一起獲得2010年IEEE頒發(fā)的約翰·馮諾依曼獎(jiǎng)，以表彰其“為自動(dòng)機(jī)和語(yǔ)言理論領(lǐng)域奠定基礎(chǔ)，以及對(duì)理論計(jì)算機(jī)科學(xué)的許多開(kāi)創(chuàng)性貢獻(xiàn)”。 拉杰夫·莫特瓦尼（Rajeev Motwani） 斯坦福大學(xué)計(jì)算機(jī)科學(xué)系教授。他的研究興趣包括數(shù)據(jù)庫(kù)、數(shù)據(jù)挖掘、Web搜索和信息檢索、機(jī)器人等。他于2009年6月意外身亡，享年47歲。 杰弗里·D.烏爾曼（Jeffrey D. Ullman） 2020年圖靈獎(jiǎng)獲得者、美國(guó)國(guó)家工程院院士、斯坦福大學(xué)計(jì)算機(jī)科學(xué)系名譽(yù)教授。他的研究興趣包括數(shù)據(jù)庫(kù)理論、數(shù)據(jù)庫(kù)集成、數(shù)據(jù)挖掘、理論計(jì)算等。他和John E. Hopcroft一起獲得2010年IEEE頒發(fā)的約翰·馮諾依曼獎(jiǎng)，以表彰其“為自動(dòng)機(jī)和語(yǔ)言理論領(lǐng)域奠定基礎(chǔ)，以及對(duì)理論計(jì)算機(jī)科學(xué)的許多開(kāi)創(chuàng)性貢獻(xiàn)”。
書(shū)友推薦
- >
我從未如此眷戀人間
- >
上帝之肋:男人的真實(shí)旅程
- >
隨園食單
- >
唐代進(jìn)士錄
- >
回憶愛(ài)瑪儂
- >
小考拉的故事-套裝共3冊(cè)
- >
羅庸西南聯(lián)大授課錄
- >
中國(guó)人在烏蘇里邊疆區(qū):歷史與人類(lèi)學(xué)概述
本類(lèi)暢銷(xiāo)
