自動機理論、語言和計算導論

《自動機理論、語言和計算導論》是2008年機械工業出版社出版的圖書，作者是霍普克羅夫特 (John E.Hopcroft）。

基本介紹

• 書名：自動機理論、語言和計算導論
• 作者：霍普克羅夫特 (John E.Hopcroft）
• 譯者：孫家嘯
• ISBN：9787111240358
• 定價：49.00 元
• 出版社：機械工業出版社
• 出版時間：2008
• 開本：16

內容簡介

本書是關於形式語言、自動機理論和計算複雜性方面的經典之作，是國際上得到廣泛認可的計算機理論和計算機工程專業的優秀教材。書中涵蓋了有窮自動機、正則表達式與語言、正則語言的性質、上下文無關文法及上下文無關語言、下推自動機、上下文無關語言的性質、圖靈機、不可判定性以及難解問題等內容。本書注重定義、定理的準確性和嚴格性，注重學生形式化和嚴格的數學推理能力的培養，同時在定義和證明中運用直觀的方法說明抽象概念，藉助許多圖表幫助傳達思想，並包含大量難度各異的示例和習題，便於讀者加深對內容的理解。

本書適合作為計算機專業高年級本科生及研究生計算理論課程的教材和教學參考書。

編輯推薦

本書是關於形式語言、自動機理論和計算複雜性方面的經典教材，是三位理論計算大師的巔峰之作，現已更新到第3版。書中涵蓋了有窮自動機、正則表達式與語言、正則語言的性質、上下文無關文法及上下文無關語言、下推自動機、上下文無關語言的性質、圖靈機、不可判定性以及難解問題等內容。

本書已被世界許多著名大學採用為計算機理論課程的教材或教學參考書，適合作為國內高校計算機專業高年級本科生或研究生的教材，還可供從事理論計算工作的研究人員參考。

本書特點： 以簡潔和易理解的方式講述理論概念；強調理論的現代套用；使用大量的圖來幫助表達概念；提供定義和證明的更多細節； 每章提供大量難易程度不同的練習。

作者簡介

John E.Hopcroft 於史丹福大學獲得博士學位，現為康奈爾大學計算機科學系教授。1994年到2001年，任康奈爾大學工程學院院長。他是1986年圖靈獎獲得者。他的研究興趣集中在計算理論方面，尤其是算法分析、自動機理論等。

Rajeev Motwani 於加州大學伯克利分校獲得博士學位，現為史丹福大學計算機科學系教授。他的研究興趣包括：資料庫、數據挖掘，Web搜尋和信息檢索、機器人等。

Jeffrey D. Ullman 史丹福大學計算機科學系 Stanford W. Ascherman 教授，資料庫專家，美國國家工程院院士。他的研究興趣包括：資料庫理論、資料庫集成、數據挖掘、理論計算等。

目錄

出版者的話

譯者序

前言

第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.2DFA如何處理串

2.2.3DFA的簡化記號

2.2.4把轉移函式擴展到串

2.2.5DFA的語言

2.2.6習題

2.3非確定型有窮自動機

2.3.1非確定型有窮自動機的非形式化觀點

2.3.2非確定型有窮自動機的定義

2.3.3擴展轉移函式

2.3.4NFA的語言

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.1e轉移的用途

2.5.2e-NFA的形式化定義

2.5.3e閉包

2.5.4e-NFA的擴展轉移和語言

2.5.5消除e轉移

2.5.6習題

2.6小結

2.7參考文獻

第3章正則表達式與正則語言

3.1正則表達式

3.1.1正則表達式運算符

3.1.2構造正則表達式

3.1.3正則表達式運算符的優先權

3.1.4習題

3.2有窮自動機和正則表達式

3.2.1從DFA到正則表達式

3.2.2通過消除狀態把DFA轉化為正則表達式

3.2.3把正則表達式轉化為自動機

3.2.4習題

3.3正則表達式的套用

3.3.1UNIX中的正則表達式

3.3.2詞法分析

3.3.3查找文本中的模式

3.3.4習題

3.4正則表達式代數定律

3.4.1結合律與交換律

3.4.2單位元與零元

3.4.3分配律

3.4.4冪等律

3.4.5與閉包有關的定律

3.4.6發現正則表達式定律

3.4.7檢驗正則表達式代數定律

3.4.8習題

3.5小結

3.6參考文獻

第4章正則語言的性質

第5章上下文無關文法及上下文無關語言

第6章下推自動機

第7章上下文無關語言的性質

第8章圖靈機導引

第9章不可判定性

第10章難解問題

第11章其他問題類

索引