本書是關于形式語言、自動機理論和計算復雜性方面的經典之作，是國際上得到廣泛認可的計算機理論和計算機工程專業的教材。書中涵蓋了有窮自動機、正則表達式與語言、正則語言的性質、上下文無關文法及上下文無關語言、下推自動機、上下文無關語言的性質、圖靈機、不可判定性以及難解問題等內容。本書注重定義、定理的性和嚴格性，注重學生形式化和嚴格的數學推理能力的培養，同時在定義和證明中運用直觀的方法說明抽象概念，借助許多圖表幫助傳達思想，并包含大量難度各異的示例和習題，便于讀者加深對內容的理解。
本書適合作為計算機專業高年級本科生及研究生計算理論課程的教材和教學參考書。
本書是關于形式語言、自動機理論和計算復雜性方面的經典教材，是三位理論計算大師的之作，現已更新到第3版。書中涵蓋了有窮自動機、正則表達式與語言、正則語言的性質、上下文無關文法及上下文無關語言、下推自動機、上下文無關語言的性質、圖靈機、不可判定性以及難解問題等內容。
本書已被世界許多著名大學采用為計算機理論課程的教材或教學參考書，適合作為國內高校計算機專業高年級本科生或研究生的教材，還可供從事理論計算工作的研究人員參考。
本書特點： 以簡潔和易理解的方式講述理論概念；強調理論的現代應用；使用大量的圖來幫助表達概念；提供定義和證明的更多細節； 每章提供大量難易程度不同的練習。
Hopcroft，J.E，地斯坦福大學獲得博士學位，現為康奈爾大任康奈爾大學工程學院院長。他是1986年圖靈獎獲得者。他的研究興趣集中在計算理論方面，尤其是算法分析、自動機理論等。
出版者的話
譯者序
前言
第1章 自動機：方法與體驗
1.1 為什么研究自動機理論
1.1.1 有窮自動機簡介
1.1.2 結構表示法
1.1.3 自動機與復雜性
1.2 形式化證明簡介
1.2.1 演繹證明
1.2.2 求助于定義
1.2.3 其他定理形式
1.2.4 表面上不是"如果-則"命題的定理
1.3 其他的證明形式
1.3.1 證明集合等價性
1.3.2 逆否命題
1.3.3 反證法
1.3.4 反例
1.4 歸納證明
1.4.1 整數上的歸納法
1.4.2 更一般形式的整數歸納法
1.4.3 結構歸納法
1.4.4 互歸納法
1.5 自動機理論的中心概念
1.5.1 字母表
1.5.2 串
1.5.3 語言
1.5.4 問題
1.6 小結
1.7 參考文獻
第2章 有窮自動機
2.1 有窮自動機的非形式化描述
2.1.1 基本規則
2.1.2 協議
2.1.3 允許自動機忽略動作
2.1.4 整個系統成為一個自動機
2.1.5 用乘積自動機驗證協議
2.2 確定型有窮自動機
2.2.1 確定型有窮自動機的定義
2.2.2 DFA如何處理串
2.2.3 DFA的簡化記號
2.2.4 把轉移函數擴展到串
2.2.5 DFA的語言
2.2.6 習題
2.3 非確定型有窮自動機
2.3.1 非確定型有窮自動機的非形式化觀點
2.3.2 非確定型有窮自動機的定義
2.3.3 擴展轉移函數
2.3.4 NFA的語言
2.3.5 確定型有窮自動機與非確定型有窮自動機的等價性
2.3.6 子集構造的壞情形
2.3.7 習題
2.4 應用：文本搜索
2.4.1 在文本中查找串
2.4.2 文本搜索的非確定型有窮自動機
2.4.3 識別關鍵字集合的DFA
2.4.4 習題
2.5 帶e 轉移的有窮自動機
2.5.1 e 轉移的用途
2.5.2 e-NFA的形式化定義
2.5.3 e 閉包
2.5.4 e-NFA的擴展轉移和語言
2.5.5 消除 e 轉移
2.5.6 習題
2.6 小結
2.7 參考文獻
第3章 正則表達式與正則語言
……
第4章 正則語言的性質
第5章 上下文無關文法及上下文無關語言
第6章 下推自動機
第7章 上下文無關語言的性質
第8章 圖靈機導引
第9章 不可判定性
第10章 難解問題
第11章 其他問題類
索引
第1章 自動機：方法與體驗
自動機理論研究抽象計算裝置或"機器"。在20世紀30年代計算機出現之前，圖靈研究過一種抽象機器，這種機器具備了今天計算機的所有能力，至少在計算能力上是這樣的。圖靈的目標是地描述一條界線，這條界線區分計算機能做什么和不能做什么；圖靈的結論不僅適用于抽象的圖靈機，也適用于今天的真實機器。
在20世紀40和50年代，許多研究者研究過更簡單類型的機器，今天稱為"有窮自動機"。起初建議用這些自動機來為人腦功能建立模型，后來發現這些自動機對于1.1節提到的各種其他目的也極為有用。在20世紀50年代后期，語言學家喬姆斯基(N.chomsky)開始研究形式"文法"。盡管這些文法不是嚴格意義上的機器，但與抽象自動機有密切關系，而且目前是一些重要軟件部件(包括部分編譯器在內)的基礎。
在1969年，庫克(s.C00k)擴展了圖靈對什么能被計算和什么不能被計算的研究。庫克設法分離出了兩類問題：一類是計算機能有效解決的；另一類是計算機理論上能解決，但實際上要花費太長時間，以致除了非常小的問題實例以外，計算機是毫無用處的。后一類問題稱為"難解的"或"NP-難的"。計算機硬件一直遵循著計算速度呈指數增長的規律(摩爾定律)，但這也不太可能顯著地影響解決難解問題大實例的能力。
所有這些理論進展都直接影響了計算機科學家今天的工作。有些概念，比如有窮自動機和某些類型的形式文法，用于設計和構造重要類型的軟件。另一些概念，比如圖靈機，則幫助我廠n們理解能期待軟件做什么。特別是，難解問題的理論允許推斷是否有可能"正面"處理一個問題，編寫解決這個問題的程序(因為這個問題不屬于難解的一類)，或者是否需要找到某種方法來迂回處理這個難解的問題：找近似算法、用啟發式算法或者用某種其他方法來限制程序解決這個問題所花費的時間。
……
