自動(dòng)機(jī)理論、語言和計(jì)算導(dǎo)論

前言

理論計(jì)算機(jī)科學(xué)是推動(dòng)計(jì)算機(jī)技術(shù)向前發(fā)展的強(qiáng)大動(dòng)力。自動(dòng)機(jī)、形式語言、可計(jì)算性和相關(guān)方面內(nèi)容構(gòu)成的計(jì)算理論，是理論計(jì)算機(jī)科學(xué)的基礎(chǔ)內(nèi)容之一。學(xué)習(xí)、研究這些內(nèi)容，不僅為進(jìn)一步學(xué)習(xí)、研究理論計(jì)算機(jī)科學(xué)所必需，而且對(duì)增強(qiáng)形式化能力和推理能力有重要作用，這些能力對(duì)從事計(jì)算機(jī)技術(shù)中的軟件形式化等研究，是不可缺少的。本書是由JohnE．Hopcroft、RajeevMotwani和JeffreyD．Ullman三位計(jì)算機(jī)學(xué)者合作編寫的，是最著名的理論計(jì)算機(jī)科學(xué)著作之一，是世界各國廣泛采用的計(jì)算機(jī)理論專業(yè)和計(jì)算計(jì)工程專業(yè)的優(yōu)秀教材之一。它主要介紹形式語言、自動(dòng)機(jī)、可計(jì)算性和相關(guān)方面內(nèi)容。它特別注意定義、定理的準(zhǔn)確性和嚴(yán)格性，這有利于培養(yǎng)學(xué)生形式化和嚴(yán)格的數(shù)學(xué)推理的能力。本書第1版于1979年發(fā)行。它的第3版有一個(gè)新的特色，那就是增加了一套由Gradiance公司開發(fā)的在線作業(yè)幫助系統(tǒng)。教師可以利用它給學(xué)生安排課后作業(yè)，或者給那些沒有選課的學(xué)生提供一個(gè)特殊的綜合課程（不是由老師申請(qǐng)開設(shè)的課程），使得他們可以利用這些課后作業(yè)作為練習(xí)和指導(dǎo)。然而遺憾的是，Gradiance在線作業(yè)系統(tǒng)只適用于購買原版教材的北美地區(qū)學(xué)生，中國學(xué)生還不能使用這個(gè)系統(tǒng)，因此，我們?cè)诜g第3版的過程中，對(duì)涉及Gradiance系統(tǒng)的內(nèi)容進(jìn)行了刪減。引進(jìn)國外的優(yōu)秀計(jì)算機(jī)教材，無疑會(huì)對(duì)我國的計(jì)算機(jī)教育事業(yè)的發(fā)展起積極推動(dòng)作用，也是與世界接軌、建立世界一流大學(xué)不可缺少的條件。我們把本書介紹給國內(nèi)從事計(jì)算機(jī)教育事業(yè)的同行們，以供參考。這個(gè)譯本是根據(jù)原書第3版翻譯的。參加本書翻譯的有：孫家骕同志，負(fù)責(zé)各章譯稿的詳細(xì)修改和全書的統(tǒng)稿；劉明浩同志，負(fù)責(zé)第1～3章及前言、目錄的翻譯；孫自然同志，負(fù)責(zé)第4、5章的翻譯；王嘯吟同志，負(fù)責(zé)第6、7章的翻譯；王華同志，負(fù)責(zé)第8、9章的翻譯；侯?yuàn)檴櫷?，?fù)責(zé)第10、11章及索引的翻譯。為了與本書第2版中譯本用的名詞、術(shù)語保持統(tǒng)一，在翻譯過程中我們參考了由劉田、姜暉和王捍貧同志完成的本書第2版中譯本。由于我們的能力有限，難免有不當(dāng)之處，敬請(qǐng)讀者不吝賜教。

內(nèi)容概要

本書是關(guān)于形式語言、自動(dòng)機(jī)理論和計(jì)算復(fù)雜性方面的經(jīng)典之作，是國際上得到廣泛認(rèn)可的計(jì)算機(jī)理論和計(jì)算機(jī)工程專業(yè)的優(yōu)秀教材。書中涵蓋了有窮自動(dòng)機(jī)、正則表達(dá)式與語言、正則語言的性質(zhì)、上下文無關(guān)文法及上下文無關(guān)語言、下推自動(dòng)機(jī)、上下文無關(guān)語言的性質(zhì)、圖靈機(jī)、不可判定性以及難解問題等內(nèi)容。本書注重定義、定理的準(zhǔn)確性和嚴(yán)格性，注重學(xué)生形式化和嚴(yán)格的數(shù)學(xué)推理能力的培養(yǎng)，同時(shí)在定義和證明中運(yùn)用直觀的方法說明抽象概念，借助許多圖表幫助傳達(dá)思想，并包含大量難度各異的示例和習(xí)題，便于讀者加深對(duì)內(nèi)容的理解。    本書適合作為計(jì)算機(jī)專業(yè)高年級(jí)本科生及研究生計(jì)算理論課程的教材和教學(xué)參考書。

作者簡介

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

書籍目錄

出版者的話譯者序前言第1章 自動(dòng)機(jī)：方法與體驗(yàn)　1.1 為什么研究自動(dòng)機(jī)理論　　1.1.1 有窮自動(dòng)機(jī)簡介　　1.1.2 結(jié)構(gòu)表示法　　1.1.3 自動(dòng)機(jī)與復(fù)雜性　1.2 形式化證明簡介　　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的簡化記號(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á)式與正則語言　　……第4章 正則語言的性質(zhì)第5章 上下文無關(guān)文法及上下文無關(guān)語言第6章 下推自動(dòng)機(jī)第7章 上下文無關(guān)語言的性質(zhì)第8章 圖靈機(jī)導(dǎo)引第9章 不可判定性第10章 難解問題第11章 其他問題類索引

章節(jié)摘錄

插圖：第1章 自動(dòng)機(jī)：方法與體驗(yàn)自動(dòng)機(jī)理論研究抽象計(jì)算裝置或“機(jī)器”。在20世紀(jì)30年代計(jì)算機(jī)出現(xiàn)之前，圖靈研究過一種抽象機(jī)器，這種機(jī)器具備了今天計(jì)算機(jī)的所有能力，至少在計(jì)算能力上是這樣的。圖靈的目標(biāo)是精確地描述一條界線，這條界線區(qū)分計(jì)算機(jī)能做什么和不能做什么；圖靈的結(jié)論不僅適用于抽象的圖靈機(jī)，也適用于今天的真實(shí)機(jī)器。在20世紀(jì)40和50年代，許多研究者研究過更簡單類型的機(jī)器，今天稱為“有窮自動(dòng)機(jī)”。起初建議用這些自動(dòng)機(jī)來為人腦功能建立模型，后來發(fā)現(xiàn)這些自動(dòng)機(jī)對(duì)于1.1節(jié)提到的各種其他目的也極為有用。在20世紀(jì)50年代后期，語言學(xué)家喬姆斯基（N.chomsky）開始研究形式“文法”。盡管這些文法不是嚴(yán)格意義上的機(jī)器，但與抽象自動(dòng)機(jī)有密切關(guān)系，而且目前是一些重要軟件部件（包括部分編譯器在內(nèi)）的基礎(chǔ)。在1969年，庫克（s.C00k）擴(kuò)展了圖靈對(duì)什么能被計(jì)算和什么不能被計(jì)算的研究。庫克設(shè)法分離出了兩類問題：一類是計(jì)算機(jī)能有效解決的；另一類是計(jì)算機(jī)理論上能解決，但實(shí)際上要花費(fèi)太長時(shí)間，以致除了非常小的問題實(shí)例以外，計(jì)算機(jī)是毫無用處的。后一類問題稱為“難解的”或“NP-難的”。計(jì)算機(jī)硬件一直遵循著計(jì)算速度呈指數(shù)增長的規(guī)律（摩爾定律），但這也不太可能顯著地影響解決難解問題大實(shí)例的能力。所有這些理論進(jìn)展都直接影響了計(jì)算機(jī)科學(xué)家今天的工作。有些概念，比如有窮自動(dòng)機(jī)和某些類型的形式文法，用于設(shè)計(jì)和構(gòu)造重要類型的軟件。另一些概念，比如圖靈機(jī)，則幫助我廠n們理解能期待軟件做什么。特別是，難解問題的理論允許推斷是否有可能“正面”處理一個(gè)問題，編寫解決這個(gè)問題的程序（因?yàn)檫@個(gè)問題不屬于難解的一類），或者是否需要找到某種方法來迂回處理這個(gè)難解的問題：找近似算法、用啟發(fā)式算法或者用某種其他方法來限制程序解決這個(gè)問題所花費(fèi)的時(shí)間。

編輯推薦

《自動(dòng)機(jī)理論、語言和計(jì)算導(dǎo)論》已被世界許多著名大學(xué)采用為計(jì)算機(jī)理論課程的教材或教學(xué)參考書，適合作為國內(nèi)高校計(jì)算機(jī)專業(yè)高年級(jí)本科生或研究生的教材，還可供從事理論計(jì)算工作的研究人員參考。以簡潔和易理解的方式講述理論概念。 強(qiáng)調(diào)理論的現(xiàn)代應(yīng)用。 使用大量的圖來幫助表達(dá)概念。 提供定義和證明的更多細(xì)節(jié)。 每章提供大量難易程度不同的練習(xí)。

圖書封面

圖書標(biāo)簽Tags

無

評(píng)論、評(píng)分、閱讀與下載

---

    自動(dòng)機(jī)理論、語言和計(jì)算導(dǎo)論 PDF格式下載

---