九九热精品免费观看,在线观看亚洲国语,久综合网日韩在线第一页

內(nèi)容簡介

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

作者簡介

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

圖書目錄

目錄
譯者序
前言
理論部分
第 1 章計(jì)算理論概論　　　　　　 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 自動機(jī)　　　　　　　 24
1.3 應(yīng)用 *　　　　　　　　 27
第 2 章有窮自動機(jī)　　　　　　　 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 確定與非確定的有窮接受器的
等價(jià)性　　　　　　　　 51
2.4 減少有窮自動機(jī)中狀態(tài)的
化簡 *　　　　　　　　 58
第 3 章正則語言和正則文法　　　　 64
3.1 正則表達(dá)式.　　　　　　　64
3.1.1 正則表達(dá)式的形式定義　　 64
3.1.2 正則表達(dá)式所關(guān)聯(lián)的語言　　 65
3.2 正則表達(dá)式和正則語言的
聯(lián)系　　　　　　　　　　70
3.2.1 正則表達(dá)式表示正則語言　　 70
3.2.2 正則語言的正則表達(dá)式　　 72
3.2.3 描述簡單模式的正則表達(dá)式　 77
3.3 正則文法　　　　　　　　 80
3.3.1 左線性文法和右線性文法　　 80
3.3.2 右線性文法生成正則語言　　 81
3.3.3 正則語言的右線性文法　　 83
3.3.4 正則語言和正則文法的
等價(jià)性　　　　　　　　 85
第 4 章正則語言的性質(zhì)　　　　　 89
4.1 正則語言的封閉性　　　　　 90
4.1.1 簡單集合運(yùn)算的封閉性　　 90
4.1.2 其他運(yùn)算的封閉性　　　　 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è)計(jì)
語言　　　　　　　　　 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 章下推自動機(jī)　　　　　　 159
7.1 非確定的下推自動機(jī)　　　 160
7.1.1 下推自動機(jī)的定義　　　 160
7.1.2 下推自動機(jī)接受的語言　　　163
7.2 下推自動機(jī)和上下文無關(guān)
語言　　　　　　　　　 168
7.2.1 上下文無關(guān)語言對應(yīng)的下推
自動機(jī)　　　　　　 168
7.2.2 下推自動機(jī)對應(yīng)的上
下文無關(guān)文法　　　　　　173
7.3 確定的下推自動機(jī)和確定的
上下文無關(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 章圖靈機(jī)　　　　　　　　　204
9.1 標(biāo)準(zhǔn)的圖靈機(jī)　　　　　　 204
9.1.1 圖靈機(jī)的定義　　　　　205
9.1.2 作為語言接受器的圖靈機(jī)　 209
9.1.3 作為轉(zhuǎn)換器的圖靈機(jī)　　　 212
9.2 完成復(fù)雜任務(wù)的組合圖靈機(jī)　218
9.3 圖靈論題　　　　　　　　　222
第 10 章圖靈機(jī)的其他模型　　　　 225
10.1 對圖靈機(jī)的小改動　　　　 225
10.1.1 自動機(jī)類的等價(jià)性　　　　226
10.1.2 可駐停圖靈機(jī)　　　　226
10.1.3 半無窮帶圖靈機(jī)　　　　 228
10.1.4 離線圖靈機(jī)　　　　　　 229
10.2 具有更復(fù)雜存儲的圖靈機(jī)　　232
10.2.1 多帶圖靈機(jī)　　　　　　 232
10.2.2 多維圖靈機(jī)　　　　　　 234
10.3 非確定的圖靈機(jī)　　　　　 236<>