该书是关于形式语言、自动机理论和计算复杂性方面的经典教材，是三位理论计算大师的之作，现已更新到第3版。书中涵盖了有穷自动机、正则表达式与语言、正则语言的性质、上下文无关文法及上下文无关语言、下推自动机的，陆质、图灵机、不可判定性以及难解问题等内容。该书已被世界许多著名大学采用为计算机理论课程的教材或教学参考书，适合用作国内高校计算机专业高年级本科生或研究生的教材，还可供从事理论计算工作的研究人员参考。

内容提要

作者简介

目录

作者：（美）霍普克罗夫特（Hopcroft，J.E.）　等著

ISBN：第一版[7111223926] 第三版[9787111223924]

出版社：机械工业出版社

出版日期：2007-9-1

定价：￥59.00元

内容提要

本书已被世界许多著名大学采用为计算机理论课程的教材或教学参考书，适合用作国内高校计算机专业高年级本科生或研究生的教材，还可供从事理论计算工作的研究人员参考。

作者简介

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