形式語言與自動機導論（原書第7版）

定　價：￥129.00

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

購買這本書可以去

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

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

內容簡介

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

作者簡介

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

圖書目錄

目錄
譯者序
前言
理論部分
第 1 章計算理論概論　　　　　　 2
1.1 數(shù)學預備知識和符號表示　　　 3
1.1.1 集合　　　　　　　　　3
1.1.2 函數(shù)和關系　　　　　　　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 應用 *　　　　　　　　 27
第 2 章有窮自動機　　　　　　　 33
2.1 確定的有窮接受器　　　　　 33
2.1.1 確定的接受器和轉移圖　　 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 正則表達式所關聯(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 章正則語言的性質　　　　　 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 章上下文無關語言　　　　　　113
5.1 上下文無關文法　　　　　　114
5.1.1 上下文無關文法示例　　　 114
5.1.2 最左推導和最右推導　　　 116
5.1.3 推導樹　　　　　　 117
5.1.4 句型和推導樹的關系　　　 119
5.2 解析和歧義性　　　　　　 123
5.2.1 解析和成員資格　　　　　123
5.2.2 文法和語言的歧義性　　　 127
5.3 上下文無關文法和程序設計
語言　　　　　　　　　 132
第 6 章上下文無關文法的化簡和
范式　　　　　　　　　　135
6.1 文法轉換的方法　　　　　　136
6.1.1 有用的代入規(guī)則　　　　　136
6.1.2 消除無用的產生式　　　 138
6.1.3 消除 λ-產生式　　　　 141
6.1.4 消除單元產生式　　　　　143
6.2 兩種重要的范式　　　　　　149
6.2.1 喬姆斯基范式　　　　　150
6.2.2 格雷巴赫范式　　　　　152
6.3 上下文無關文法的成員資格
判定算法 *　　　　　　　 156
第 7 章下推自動機　　　　　　 159
7.1 非確定的下推自動機　　　 160
7.1.1 下推自動機的定義　　　 160
7.1.2 下推自動機接受的語言　　　163
7.2 下推自動機和上下文無關
語言　　　　　　　　　 168
7.2.1 上下文無關語言對應的下推
自動機　　　　　　 168
7.2.2 下推自動機對應的上
下文無關文法　　　　　　173
7.3 確定的下推自動機和確定的
上下文無關語言　　　　　　179
7.4 確定的上下文無關語言的
文法 *　　　　　　　　　184
第 8 章上下文無關語言的性質　　　 188
8.1 兩個泵引理　　　　　　 188
8.1.1 上下文無關語言的泵引理　 189
8.1.2 線性語言的泵引理　　　 192
8.2 上下文無關語言的封閉性
和判定算法　　　　　　 196
8.2.1 上下文無關語言的封閉性　 197
8.2.2 上下文無關語言的一些可判
定性質　　　　　　 200
第 9 章圖靈機　　　　　　　　　204
9.1 標準的圖靈機　　　　　　 204
9.1.1 圖靈機的定義　　　　　205
9.1.2 作為語言接受器的圖靈機　 209
9.1.3 作為轉換器的圖靈機　　　 212
9.2 完成復雜任務的組合圖靈機　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 具有更復雜存儲的圖靈機　　232
10.2.1 多帶圖靈機　　　　　　 232
10.2.2 多維圖靈機　　　　　　 234
10.3 非確定的圖靈機　　　　　 236<>