自動機理論、語言和計算機導論（英文版·第3版）

該書是關於形式語言、自動機理論和計算複雜性方面的經典教材，是三位理論計算大師的之作，現已更新到第3版。書中涵蓋了有窮自動機、正則表達式與語言、正則語言的性質、上下文無關文法及上下文無關語言、下推自動機的，陸質、圖靈機、不可判定性以及難解問題等內容。該書已被世界許多著名大學採用為計算機理論課程的教材或教學參考書，適合用作國內高校計算機專業高年級本科生或研究生的教材，還可供從事理論計算工作的研究人員參考。

基本介紹

• 書名：自動機理論、語言和計算機導論(英文版·第3版)
• 作者：（美）霍普克羅夫特（Hopcroft，J.E.）
• ISBN：9787111223924，7111223926
• 定價：￥59.00元
• 出版社：機械工業出版社
• 出版時間：2007-9-1

內容提要

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

作者簡介

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

目錄

1Automata:TheMethodsandtheMadness

1.1WhyStudyAutomataTheory?

1.1.1IntroductiontoFiniteAutomata

1.1.2StructuralRepresentations

1.1.3AutomataandComplexity

1.2IntroductiontoFormalProof

1.2.1DeductiveProofs

1.2.2ReductiontoDefinitions

1.2.3OtherTheoremForms

1.2.4TheoremsThatAppearNottoBeIf-ThenStatements

1.3AdditionalFormsofProof

1.3.1ProvingEquivalencesAboutSets

1.3.2TheContrapositive

1.3.3ProofbyContradiction

1.3.4Counterexamples

1.4InductiveProofs

1.4.1InductionsonIntegers

1.4.2MoreGeneralFormsofIntegerInductions

1.4.3StructuralInductions

1.4.4MutualInductions

1.5TheCentralConceptsofAutomataTheory

1.5.1Alphabets

1.5.2,Strings

1.5.3Languages

1.5.4Problems

1.6SummaryofChapter1

1.7GradianceProblemsforChapter1

1.8ReferencesforChapter1

2FiniteAutomata

2.1AnInformalPictureofFiniteAutomata

2.1.1TheGroundRules

2.1.2TheProtocol

2.1.3EnablingtheAutomatatoIgnoreActions

2.1.4TheEntireSystemasanAutomaton

2.1.5UsingtheProductAutomatontoValidatetheProtocol

2.2DeterministicFiniteAutomata

2.2.1DefinitionofaDeterministicFiniteAutomaton

2.2.2HowaDFAProcessesStrings

2.2.3SimplerNotationsforDFA's

2.2.4ExtendingtheTransitionFunctiontoStrings

2.2.5TheLanguageofaDFA

2.2.6ExercisesforSection2.2

2.3NondeterministicFiniteAutomata

2.3.1AnInformalViewofNondeterministicFiniteAutomata

2.3.2DefinitionofNondeterministicFiniteAutomata

2.3.3TheExtendedTransitionFunction

2.3.4TheLanguageofanNFA

2.3.5EquivalenceofDeterministicandNondeterministicFiniteAutomata

2.3.6ABadCasefortheSubsetConstruction

2.3.7ExercisesforSection2.3

2.4AnApplication:TextSearch

2.4.1FindingStringsinText

2.4.2NondeterministicFiniteAutomataforTextSearch

2.4.3ADFAtoRecognizeaSetofKeywords

2.4.4ExercisesforSection2.4

2.5FiniteAutomataWithEpsilon-Transitions

2.5.1Usesofe-Transitions

2.5.2TheFormalNotationforanc-NFA

2.5.3Epsilon-Closures

2.5.4ExtendedTransitionsandLanguagesforc-NFA's

2.5.5Eliminatinge-Transitions

2.5.6ExercisesforSection2.5

2.6SummaryofChapter2

2.7GradianceProblemsforChapter2

2.8ReferencesforChapter2

3RegularExpressionsandLanguages

3.1RegularExpressions

3.1.1TheOperatorsofRegularExpressions

3.1.2BuildingRegularExpressions

3.1.3PrecedenceofRegular-ExpressionOperators

3.1.4ExercisesforSection3.1

3.2FiniteAutomataandRegularExpressions

3.2.1FromDFA'stoRegularExpressions

3.2.2ConvertingDFA'stoRegularExpressionsbyEliminatingStates

……

4PropertieskfRegularLanguages

5Context-FreeGrammarsandLanguages

6PushdownAutomata

7PropertiesofContext-FreeLanguages

8IntroductiontoTuringMachines

9Undecidability

10IntractableProblems

11AdditionalClassesofProblems

Index