語(yǔ)言與機(jī)器計(jì)算機(jī)科學(xué)理論導(dǎo)論（原書第3版）

出版者的話
專家指導(dǎo)委員會(huì)
譯者序
前言
緒論
第一部分 基礎(chǔ)
第1章 數(shù)學(xué)預(yù)備知識(shí)
　1.1　集合論
　1.2　笛卡兒積、關(guān)系和函數(shù)
　1.3　等價(jià)關(guān)系
　1.4　可數(shù)集合和不可數(shù)集合
　1.5　對(duì)角化和自反
　1.6　遞歸定義
　1.7　數(shù)學(xué)歸納
　1.8　有向圖
　1.9　練習(xí)
　參考文獻(xiàn)注釋
第2章 語(yǔ)言
　2.1　字符串和語(yǔ)言
　2.2　語(yǔ)言的有窮規(guī)格說(shuō)明
　2.3　正則集合和表達(dá)式
　2.4　正則表達(dá)式和文本搜索
　2.5　練習(xí)
參考文獻(xiàn)注釋
第二部分 文法、自動(dòng)機(jī)和語(yǔ)言
第3章 上下文無(wú)關(guān)文法
　3.1　上下文無(wú)關(guān)文法和語(yǔ)言
　3.2　文法和語(yǔ)言的例子
　3.3　正則文法
　3.4　驗(yàn)證文法
　3.5　最左推導(dǎo)和二義性
　3.6　上下文無(wú)關(guān)文法和編程語(yǔ)言定義
　3.7　練習(xí)
　參考文獻(xiàn)注釋
第4章 上下文無(wú)關(guān)文法范式
　4.1　文法轉(zhuǎn)換
　4.2　消去入規(guī)則
　4.3　去掉鏈規(guī)則
　4.4　無(wú)用符
　4.5　喬姆斯基范式
　4.6　CYK算法
　4.7　去掉直接左遞歸
　4.8　格立巴赫范式
　4.9　練習(xí)
　參考文獻(xiàn)注釋
第5章 有限自動(dòng)機(jī)
　5.1 一個(gè)有限狀態(tài)自動(dòng)機(jī)
　5.2 確定型有限自動(dòng)機(jī)
　5.3 狀態(tài)圖和例子
　5.4 非確定型有限自動(dòng)機(jī)
　5.5 λ-轉(zhuǎn)換
　5.6 去掉非確定性
　5.7 DFA的最小化
　5.8 練習(xí)
　參考文獻(xiàn)注釋
第6章 正則語(yǔ)言的性質(zhì)
　6.1 有限狀態(tài)機(jī)接收正則語(yǔ)言
　6.2 表達(dá)式圖
　6.3 正則文法和有限自動(dòng)機(jī)
　6.4 正則語(yǔ)言的封閉性質(zhì)
　6.5 非正則語(yǔ)言
　6.6 規(guī)則語(yǔ)言的泵引理
　6.7 Myhill-Nerode定理
　6.8 練習(xí)
　參考文獻(xiàn)注釋
第7章 下推自動(dòng)機(jī)和上下文無(wú)關(guān)語(yǔ)言
7.1 下推自動(dòng)機(jī)
7.2 PDA的變種
7.3 上下文無(wú)關(guān)語(yǔ)言的接收
7.4 上下文無(wú)關(guān)語(yǔ)言的泵引理
7.5 上下文無(wú)關(guān)語(yǔ)言的封閉性
7.6　練習(xí)
參考文獻(xiàn)注釋
第三部分 可計(jì)算性
第8章 圖靈機(jī)
8.1　標(biāo)準(zhǔn)圖靈機(jī)
8.2　作為語(yǔ)言接收器的圖靈機(jī)
8.3　可供選擇接收標(biāo)準(zhǔn)
8.4　多道圖靈機(jī)
8.5　雙向圖靈機(jī)
8.6　多帶圖靈機(jī)
8.7　非確定型圖靈機(jī)
8.8　用來(lái)枚舉語(yǔ)言的圖靈機(jī)
8.9　練習(xí)
參考文獻(xiàn)注釋
第9章 圖靈可計(jì)算函數(shù)
9.1　函數(shù)的計(jì)算
9.2　數(shù)值計(jì)算
9.3　圖靈機(jī)的順序操作
9.4　函數(shù)的合成
9.5　不可計(jì)算函數(shù)
9.6　關(guān)于編程語(yǔ)言
9.7　練習(xí)
參考文獻(xiàn)注釋
第10章 喬姆斯基層次
10.1　無(wú)限制文法
10.2　上下文有關(guān)文法
10.3　線性有界自動(dòng)機(jī)
10.4　喬姆斯基層次
10.5　練習(xí)
參考文獻(xiàn)注釋
第11章 判定問(wèn)題與丘奇—圖靈論題
11.1　判定問(wèn)題的描述
11.2　判定問(wèn)題和遞歸語(yǔ)言
11.3　問(wèn)題歸約
11.4　丘奇—圖靈論題
11.5　通用機(jī)
11.6　練習(xí)
參考文獻(xiàn)注釋
第12章 不可判定性
12.1　圖靈機(jī)的停機(jī)問(wèn)題
12.2　問(wèn)題歸約和不可判定性
12.3　其他的停機(jī)問(wèn)題
12.4　萊斯定理
12.5　不可解決的詞問(wèn)題
12.6　波斯特對(duì)應(yīng)問(wèn)題
12.7　上下文無(wú)關(guān)文法中的不可判定問(wèn)題
12.8　練習(xí)
參考文獻(xiàn)注釋
第13章 Mu-遞歸函數(shù)
13.1　原始遞歸函數(shù)
13.2　一些原始遞歸函數(shù)
13.3　有界操作符
13.4　除法函數(shù)
13.5　歌德?tīng)枖?shù)字和串值遞歸
13.6　可計(jì)算部分函數(shù)
13.7 圖靈可計(jì)算函數(shù)和Mu-遞歸函數(shù)
13.8　修訂的丘奇—圖靈論題
13.9　練習(xí)
參考文獻(xiàn)注釋
第四部分　計(jì)算復(fù)雜性
第14章 時(shí)間復(fù)雜性
14.1　復(fù)雜性度量
14.2　增長(zhǎng)的速度
14.3　圖靈機(jī)的時(shí)問(wèn)復(fù)雜性
14.4　復(fù)雜性和圖靈機(jī)的變種
14.5　線性加速
14.6　語(yǔ)言時(shí)間復(fù)雜性的屬性
14.7　計(jì)算機(jī)計(jì)算的模擬
14.8　練習(xí)
參考文獻(xiàn)注釋
第15章 P、NP和庫(kù)克定理
15.1 非確定型圖靈機(jī)的時(shí)間復(fù)雜性
15.2　P類和NP類
15.3　問(wèn)題表示和復(fù)雜性
15.4　判定問(wèn)題和復(fù)雜性類
15.5　哈密爾頓回路問(wèn)題
15.6　多項(xiàng)式時(shí)間歸約
15.7 P=NP？
15.8 可滿足性問(wèn)題
15.9 復(fù)雜類的關(guān)系
15.10　練習(xí)
參考文獻(xiàn)注釋
第16章 NP-完全問(wèn)題
16.1　歸約和NP-完全問(wèn)題
16.2　三元可滿足性問(wèn)題
16.3　三元可滿足性的歸約
16.4　歸約和子問(wèn)題
16.5　最優(yōu)化問(wèn)題
16.6　近似算法
16.7　近似方案
16.8　練習(xí)
參考文獻(xiàn)注釋
第17章 其他復(fù)雜性類
17.1 派生的復(fù)雜性類
17.2 空間復(fù)雜性
17.3 空間復(fù)雜性和時(shí)間復(fù)雜性的關(guān)系
17.4 P-空間，NP-空間和薩維奇定理
17.5 P-空間完全性
17.6 一個(gè)難解問(wèn)題
17.7 練習(xí)
參考文獻(xiàn)注釋
第五部分　確定型語(yǔ)法分析
第18章　語(yǔ)法分析引論
18.1 文法圖
18.2　自頂向下語(yǔ)法分析
18.3　歸約和自底向上語(yǔ)法分析
18.4　自底向上語(yǔ)法分析器
18.5　語(yǔ)法分析和編譯
18.6　練習(xí)
參考文獻(xiàn)注釋
第19章　LL(k)文法
19.1 上下文無(wú)關(guān)文法中的預(yù)讀
19.2 FIRST集合、FOLLOW集合和預(yù)讀集合
　19.3 強(qiáng)LL(k)語(yǔ)法
　19.4 FIRSTk集合的構(gòu)造
　19.5 FOLLOWk集合的構(gòu)造
　19.6 強(qiáng)LL(1)文法
　19.7 強(qiáng)LL(k)分析器
　19.8 LL(k)文法
　19.9 練習(xí)
　參考文獻(xiàn)注釋
第20章 LR(k)文法
20.1 LR(0)上下文
20.2 LR(0)分析器
20.3 LR(0)機(jī)
20.4 被LR(0)機(jī)接收
20.5 LR(1)文法
20.6 練習(xí)
參考文獻(xiàn)注釋
附錄Ⅰ 標(biāo)記索引
附錄Ⅱ 希臘字母表
附錄Ⅲ ASC Ⅱ字符集
附錄Ⅲ Java的BNF范式定義
參考文獻(xiàn)
索引