形式語言與自動機導(dǎo)論（原書第7版）

定　價：￥129.00

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

購買這本書可以去

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

ISBN：	9787111767527	出版時間：	2025-02-01	包裝：	平裝-膠訂
開本：	16開	頁數(shù)：		字數(shù)：

內(nèi)容簡介

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

作者簡介

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

圖書目錄

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