自動(dòng)機(jī)理論、語言和計(jì)算導(dǎo)論（原書第3版）

定　價(jià)：￥49.00

作　者：	（美）霍普克羅夫特（Hopcroft，J.E）等著；孫家骕等譯
出版社：	機(jī)械工業(yè)出版社
叢編項(xiàng)：	計(jì)算機(jī)科學(xué)叢書
標(biāo)　簽：	計(jì)算機(jī)理論

購買這本書可以去

ISBN：	9787111240358	出版時(shí)間：	2008-07-01	包裝：	平裝
開本：	16開	頁數(shù)：	366	字?jǐn)?shù)：

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

　　本書是關(guān)于形式語言、自動(dòng)機(jī)理論和計(jì)算復(fù)雜性方面的經(jīng)典教材，是三位理論計(jì)算大師的巔峰之作，現(xiàn)已更新到第3版。書中涵蓋了有窮自動(dòng)機(jī)、正則表達(dá)式與語言、正則語言的性質(zhì)、上下文無關(guān)文法及上下文無關(guān)語言、下推自動(dòng)機(jī)、上下文無關(guān)語言的性質(zhì)、圖靈機(jī)、不可判定性以及難解問題等內(nèi)容。本書已被世界許多著名大學(xué)采用為計(jì)算機(jī)理論課程的教材或教學(xué)參考書，適合作為國內(nèi)高校計(jì)算機(jī)專業(yè)高年級(jí)本科生或研究生的教材，還可供從事理論計(jì)算工作的研究人員參考。本書特點(diǎn)：以簡(jiǎn)潔和易理解的方式講述理論概念。強(qiáng)調(diào)理論的現(xiàn)代應(yīng)用。使用大量的圖來幫助表達(dá)概念。提供定義和證明的更多細(xì)節(jié)。每章提供大量難易程度不同的練習(xí)。

作者簡(jiǎn)介

　　Hopcroft，J.E，地斯坦福大學(xué)獲得博士學(xué)位，現(xiàn)為康奈爾大任康奈爾大學(xué)工程學(xué)院院長(zhǎng)。他是1986年圖靈獎(jiǎng)獲得者。他的研究興趣集中在計(jì)算理論方面，尤其是算法分析、自動(dòng)機(jī)理論等。

圖書目錄

出版者的話
譯者序
前言
第1章自動(dòng)機(jī)：方法與體驗(yàn)
1.1 為什么研究自動(dòng)機(jī)理論
1.1.1 有窮自動(dòng)機(jī)簡(jiǎn)介
1.1.2 結(jié)構(gòu)表示法
1.1.3 自動(dòng)機(jī)與復(fù)雜性

1.2 形式化證明簡(jiǎn)介
1.2.1 演繹證明
1.2.2 求助于定義
1.2.3 其他定理形式
1.2.4 表面上不是“如果-則”命題的定理

1.3 其他的證明形式
1.3.1 證明集合等價(jià)性
1.3.2 逆否命題
1.3.3 反證法
1.3.4 反例

1.4 歸納證明
1.4.1 整數(shù)上的歸納法
1.4.2 更一般形式的整數(shù)歸納法
1.4.3 結(jié)構(gòu)歸納法
1.4.4 互歸納法

1.5 自動(dòng)機(jī)理論的中心概念
1.5.1 字母表
1.5.2 串
1.5.3 語言
1.5.4 問題
1.6 小結(jié)
1.7 參考文獻(xiàn)

第2章有窮自動(dòng)機(jī)
2.1 有窮自動(dòng)機(jī)的非形式化描述
2.1.1 基本規(guī)則
2.1.2 協(xié)議
2.1.3 允許自動(dòng)機(jī)忽略動(dòng)作
2.1.4 整個(gè)系統(tǒng)成為一個(gè)自動(dòng)機(jī)
2.1.5 用乘積自動(dòng)機(jī)驗(yàn)證協(xié)議

2.2 確定型有窮自動(dòng)機(jī)
2.2.1 確定型有窮自動(dòng)機(jī)的定義
2.2.2 DFA如何處理串
2.2.3 DFA的簡(jiǎn)化記號(hào)
2.2.4 把轉(zhuǎn)移函數(shù)擴(kuò)展到串
2.2.5 DFA的語言
2.2.6 習(xí)題

2.3 非確定型有窮自動(dòng)機(jī)
2.3.1 非確定型有窮自動(dòng)機(jī)的非形式化觀點(diǎn)
2.3.2 非確定型有窮自動(dòng)機(jī)的定義
2.3.3 擴(kuò)展轉(zhuǎn)移函數(shù)
2.3.4 NFA的語言
2.3.5 確定型有窮自動(dòng)機(jī)與非確定型有窮自動(dòng)機(jī)的等價(jià)性
2.3.6 子集構(gòu)造的壞情形
2.3.7 習(xí)題

2.4 應(yīng)用：文本搜索
2.4.1 在文本中查找串
2.4.2 文本搜索的非確定型有窮自動(dòng)機(jī)
2.4.3 識(shí)別關(guān)鍵字集合的DFA
2.4.4 習(xí)題

2.5 帶e 轉(zhuǎn)移的有窮自動(dòng)機(jī)
2.5.1 e 轉(zhuǎn)移的用途
2.5.2 e-NFA的形式化定義
2.5.3 e 閉包
2.5.4 e-NFA的擴(kuò)展轉(zhuǎn)移和語言
2.5.5 消除 e 轉(zhuǎn)移
2.5.6 習(xí)題
2.6 小結(jié)
2.7 參考文獻(xiàn)

第3章正則表達(dá)式與正則語言
3.1 正則表達(dá)式
3.1.1 正則表達(dá)式運(yùn)算符
3.1.2 構(gòu)造正則表達(dá)式
3.1.3 正則表達(dá)式運(yùn)算符的優(yōu)先級(jí)
3.1.4 習(xí)題

3.2 有窮自動(dòng)機(jī)和正則表達(dá)式
3.2.1 從DFA到正則表達(dá)式
3.2.2 通過消除狀態(tài)把DFA轉(zhuǎn)化為正則表達(dá)式
3.2.3 把正則表達(dá)式轉(zhuǎn)化為自動(dòng)機(jī)
3.2.4 習(xí)題

3.3 正則表達(dá)式的應(yīng)用
3.3.1 UNIX中的正則表達(dá)式
3.3.2 詞法分析
3.3.3 查找文本中的模式
3.3.4 習(xí)題

3.4 正則表達(dá)式代數(shù)定律
3.4.1 結(jié)合律與交換律
3.4.2 單位元與零元
3.4.3 分配律
3.4.4 冪等律
3.4.5 與閉包有關(guān)的定律
3.4.6 發(fā)現(xiàn)正則表達(dá)式定律
3.4.7 檢驗(yàn)正則表達(dá)式代數(shù)定律
3.4.8 習(xí)題
3.5 小結(jié)
3.6 參考文獻(xiàn)
第4章正則語言的性質(zhì)
第5章上下文無關(guān)文法及上下文無關(guān)語言
第6章下推自動(dòng)機(jī)
第7章上下文無關(guān)語言的性質(zhì)
第8章圖靈機(jī)導(dǎo)引
第9章不可判定性
第10章難解問題
第11章其他問題類
索引