形式語(yǔ)言與自動(dòng)機(jī)導(dǎo)論（原書(shū)第7版）

定　價(jià)：￥129.00

作　者：	[美]彼得·林茨 ,[美]蘇珊·H. 羅杰
出版社：	機(jī)械工業(yè)出版社
叢編項(xiàng)：
標(biāo)　簽：	暫缺

購(gòu)買(mǎi)這本書(shū)可以去

當(dāng)當(dāng)網(wǎng) (￥96.70)

ISBN：	9787111767527	出版時(shí)間：	2025-02-01	包裝：	平裝-膠訂
開(kāi)本：	16開(kāi)	頁(yè)數(shù)：		字?jǐn)?shù)：

內(nèi)容簡(jiǎn)介

　　本書(shū)是理論計(jì)算機(jī)科學(xué)方面的經(jīng)典教材，主要討論形式語(yǔ)言與自動(dòng)機(jī)理論、可計(jì)算性理論和計(jì)算復(fù)雜性理論等內(nèi)容。本書(shū)強(qiáng)調(diào)定義和定理的準(zhǔn)確性和嚴(yán)謹(jǐn)性，但在形式化證明中又非常注重符合直覺(jué)的理解，避免多余的數(shù)學(xué)細(xì)節(jié)。本書(shū)分為理論和應(yīng)用兩個(gè)部分：理論部分主要介紹有窮自動(dòng)機(jī)、正則語(yǔ)言和文法、上下文無(wú)關(guān)語(yǔ)言和文法、下推自動(dòng)機(jī)、圖靈機(jī)、形式語(yǔ)言和自動(dòng)機(jī)的層次結(jié)構(gòu)以及計(jì)算復(fù)雜性等內(nèi)容，應(yīng)用部分主要介紹編譯器和解析、LL解析以及LR解析。本書(shū)可幫助讀者熟悉計(jì)算機(jī)科學(xué)的基礎(chǔ)和原理，加強(qiáng)嚴(yán)格的形式化數(shù)學(xué)證明的能力，適合高等院校計(jì)算機(jī)科學(xué)及相關(guān)專業(yè)的學(xué)生學(xué)習(xí)，也適合理論計(jì)算機(jī)科學(xué)方向的研究人員參考。

作者簡(jiǎn)介

　　彼得·林茨（Peter Linz）加利福尼亞大學(xué)戴維斯分校計(jì)算機(jī)科學(xué)系榮休教授。他的研究重點(diǎn)是數(shù)值分析理論，致力于構(gòu)建可靠的數(shù)值方法并將其用于科學(xué)計(jì)算中問(wèn)題求解環(huán)境的設(shè)計(jì)。除本書(shū)外，他還著有Exploring Numerical Methods： An Introduction to Scientific Computing。他擁有威斯康星大學(xué)博士學(xué)位。蘇珊·H. 羅杰（Susan H. Rodger）杜克大學(xué)計(jì)算機(jī)科學(xué)實(shí)踐教授。她的主要貢獻(xiàn)是開(kāi)發(fā)了大量用于理論計(jì)算機(jī)科學(xué)教育的可視化和交互軟件，其中，JFLAP軟件被世界各地的大學(xué)用于形式語(yǔ)言與自動(dòng)機(jī)的實(shí)驗(yàn)教學(xué)。她曾獲得2023年ACM SIGCSE計(jì)算機(jī)科學(xué)教育杰出貢獻(xiàn)獎(jiǎng)，2019年IEEE計(jì)算機(jī)協(xié)會(huì)Taylor L. Booth教育獎(jiǎng)，2013年ACM Karl V. Karlstrom杰出教育家獎(jiǎng)，2019年杜克大學(xué)三一學(xué)院David和Janet Vaughn Brooks杰出教學(xué)獎(jiǎng)。她擁有普渡大學(xué)計(jì)算機(jī)科學(xué)博士學(xué)位。

圖書(shū)目錄

目錄
譯者序
前言
理論部分
第 1 章計(jì)算理論概論　　　　　　 2
1.1 數(shù)學(xué)預(yù)備知識(shí)和符號(hào)表示　　　 3
1.1.1 集合　　　　　　　　　3
1.1.2 函數(shù)和關(guān)系　　　　　　　5
1.1.3 圖和樹(shù)　　　　　　　 8
1.1.4 證明方法　　　　　　　 9
1.2 三個(gè)基本概念　　　　　　　15
1.2.1 語(yǔ)言　　　　　　　　　15
1.2.2 文法　　　　　　　　 19
1.2.3 自動(dòng)機(jī)　　　　　　　 24
1.3 應(yīng)用 *　　　　　　　　 27
第 2 章有窮自動(dòng)機(jī)　　　　　　　 33
2.1 確定的有窮接受器　　　　　 33
2.1.1 確定的接受器和轉(zhuǎn)移圖　　 34
2.1.2 語(yǔ)言和 DFA 的語(yǔ)言　　　　36
2.1.3 正則語(yǔ)言　　　　　　 40
2.2 非確定的有窮接受器　　　　 44
2.2.1 非確定的接受器的定義　　 44
2.2.2 為什么需要非確定性？　　 48
2.3 確定與非確定的有窮接受器的
等價(jià)性　　　　　　　　 51
2.4 減少有窮自動(dòng)機(jī)中狀態(tài)的
化簡(jiǎn) *　　　　　　　　 58
第 3 章正則語(yǔ)言和正則文法　　　　 64
3.1 正則表達(dá)式.　　　　　　　64
3.1.1 正則表達(dá)式的形式定義　　 64
3.1.2 正則表達(dá)式所關(guān)聯(lián)的語(yǔ)言　　 65
3.2 正則表達(dá)式和正則語(yǔ)言的
聯(lián)系　　　　　　　　　　70
3.2.1 正則表達(dá)式表示正則語(yǔ)言　　 70
3.2.2 正則語(yǔ)言的正則表達(dá)式　　 72
3.2.3 描述簡(jiǎn)單模式的正則表達(dá)式　 77
3.3 正則文法　　　　　　　　 80
3.3.1 左線性文法和右線性文法　　 80
3.3.2 右線性文法生成正則語(yǔ)言　　 81
3.3.3 正則語(yǔ)言的右線性文法　　 83
3.3.4 正則語(yǔ)言和正則文法的
等價(jià)性　　　　　　　　 85
第 4 章正則語(yǔ)言的性質(zhì)　　　　　 89
4.1 正則語(yǔ)言的封閉性　　　　　 90
4.1.1 簡(jiǎn)單集合運(yùn)算的封閉性　　 90
4.1.2 其他運(yùn)算的封閉性　　　　 92
4.2 正則語(yǔ)言的基本問(wèn)題　　　　 99
4.3 識(shí)別非正則語(yǔ)言　　　　　　102
4.3.1 鴿巢原理的使用　　　　　102
4.3.2 泵引理　　　　　　 103
第 5 章上下文無(wú)關(guān)語(yǔ)言　　　　　　113
5.1 上下文無(wú)關(guān)文法　　　　　　114
5.1.1 上下文無(wú)關(guān)文法示例　　　 114
5.1.2 最左推導(dǎo)和最右推導(dǎo)　　　 116
5.1.3 推導(dǎo)樹(shù)　　　　　　 117
5.1.4 句型和推導(dǎo)樹(shù)的關(guān)系　　　 119
5.2 解析和歧義性　　　　　　 123
5.2.1 解析和成員資格　　　　　123
5.2.2 文法和語(yǔ)言的歧義性　　　 127
5.3 上下文無(wú)關(guān)文法和程序設(shè)計(jì)
語(yǔ)言　　　　　　　　　 132
第 6 章上下文無(wú)關(guān)文法的化簡(jiǎn)和
范式　　　　　　　　　　135
6.1 文法轉(zhuǎn)換的方法　　　　　　136
6.1.1 有用的代入規(guī)則　　　　　136
6.1.2 消除無(wú)用的產(chǎn)生式　　　 138
6.1.3 消除 λ-產(chǎn)生式　　　　 141
6.1.4 消除單元產(chǎn)生式　　　　　143
6.2 兩種重要的范式　　　　　　149
6.2.1 喬姆斯基范式　　　　　150
6.2.2 格雷巴赫范式　　　　　152
6.3 上下文無(wú)關(guān)文法的成員資格
判定算法 *　　　　　　　 156
第 7 章下推自動(dòng)機(jī)　　　　　　 159
7.1 非確定的下推自動(dòng)機(jī)　　　 160
7.1.1 下推自動(dòng)機(jī)的定義　　　 160
7.1.2 下推自動(dòng)機(jī)接受的語(yǔ)言　　　163
7.2 下推自動(dòng)機(jī)和上下文無(wú)關(guān)
語(yǔ)言　　　　　　　　　 168
7.2.1 上下文無(wú)關(guān)語(yǔ)言對(duì)應(yīng)的下推
自動(dòng)機(jī)　　　　　　 168
7.2.2 下推自動(dòng)機(jī)對(duì)應(yīng)的上
下文無(wú)關(guān)文法　　　　　　173
7.3 確定的下推自動(dòng)機(jī)和確定的
上下文無(wú)關(guān)語(yǔ)言　　　　　　179
7.4 確定的上下文無(wú)關(guān)語(yǔ)言的
文法 *　　　　　　　　　184
第 8 章上下文無(wú)關(guān)語(yǔ)言的性質(zhì)　　　 188
8.1 兩個(gè)泵引理　　　　　　 188
8.1.1 上下文無(wú)關(guān)語(yǔ)言的泵引理　 189
8.1.2 線性語(yǔ)言的泵引理　　　 192
8.2 上下文無(wú)關(guān)語(yǔ)言的封閉性
和判定算法　　　　　　 196
8.2.1 上下文無(wú)關(guān)語(yǔ)言的封閉性　 197
8.2.2 上下文無(wú)關(guān)語(yǔ)言的一些可判
定性質(zhì)　　　　　　 200
第 9 章圖靈機(jī)　　　　　　　　　204
9.1 標(biāo)準(zhǔn)的圖靈機(jī)　　　　　　 204
9.1.1 圖靈機(jī)的定義　　　　　205
9.1.2 作為語(yǔ)言接受器的圖靈機(jī)　 209
9.1.3 作為轉(zhuǎn)換器的圖靈機(jī)　　　 212
9.2 完成復(fù)雜任務(wù)的組合圖靈機(jī)　218
9.3 圖靈論題　　　　　　　　　222
第 10 章圖靈機(jī)的其他模型　　　　 225
10.1 對(duì)圖靈機(jī)的小改動(dòng)　　　　 225
10.1.1 自動(dòng)機(jī)類的等價(jià)性　　　　226
10.1.2 可駐停圖靈機(jī)　　　　226
10.1.3 半無(wú)窮帶圖靈機(jī)　　　　 228
10.1.4 離線圖靈機(jī)　　　　　　 229
10.2 具有更復(fù)雜存儲(chǔ)的圖靈機(jī)　　232
10.2.1 多帶圖靈機(jī)　　　　　　 232
10.2.2 多維圖靈機(jī)　　　　　　 234
10.3 非確定的圖靈機(jī)　　　　　 236<>