自动机理论与应用(影印版)(大学计算机教育国外著名教材系列)
点此进入淘宝搜索页搜索分類: 图书,教材教辅与参考书,大学,计算机专业,
品牌: 里奇(Rich.E.)
基本信息·出版社：清华大学出版社
·页码：1099 页
·出版日期：2009年11月
·ISBN：9787302212935
·条形码：9787302212935
·版本：第1版
·装帧：平装
·开本：16
·正文语种：英语
·丛书名：大学计算机教育国外著名教材系列
产品信息有问题吗？请帮我们更新产品信息。
内容简介《自动机理论与应用(影印版)》阐述了计算科学的优美理论基础，通过演示计算理论在现代硬件和软件系统设计中的影响，把理论知识带到了现实实践之中。《自动机理论与应用(影印版)》介绍了关键概念的应用，为读者在实际工作中使用计算理论提供实际指导。《自动机理论与应用(影印版)》讨论的应用包括：程序设计语言、编译器、网络技术、自然语言处理、人工智能、计算生物学、安全性、博弈、商业规则建模、标识语言、Web搜索等。《自动机理论与应用(影印版)》既适合作为自动机理论课程的教程，也是相关专业人员的重要参考用书。
编辑推荐《自动机理论与应用(影印版)》：大学计算机教育国外著名教材系列
目录
Prefacexiii
Acknowledgmentsxvii
Creditsxix
PARTI:INTRODUCTION
1 WhyStudytheTheoryofComputation?
1.1 TheShelfLifeofProgrammingTools
1.2 ApplicationsoftheTheoryAreEverywhere
2 LanguagesandStrings8
2.1 Strings8
2.2 Languages10
Exercises19
3 TheBigPicture:ALanguageHierarchy
3.1 DefiningtheTask:LanguageRecognition
3.2 ThePowerofEncoding
3.3 AMachine-BasedHierarchyofLanguageClasses
3.4 ATractabilityHierarchyofLanguageClasses
Exercises
4 Computation
4.1 DecisionProcedures
4.2 DeterminismandNondeterminism
4.3 FunctionsonLanguagesandPrograms
Exercises
PARTⅡ:FINITESTATEMACHINESANDREGULARLANGUAGES
5 FiniteStateMachines
5.1 DeterministicFiniteStateMachines
5.2 TheRegularLanguages60
5.3 DesigningDeterministicFiniteStateMachines
5.4 NondeterministicFSMs
5.5 FromFSMstoOperationalSystems
5.6 SimulatorsforFSMs
5.7 MinimizingFSMs
5.8 ACanonicalForm~orRegularLanguages
5.9 FiniteStateTransducers
5.1 0BidirectionalTransducers
5.1 1StochasticFiniteAutomata:MarkovModelsandHMMs
5.1 2FiniteAutomata,InfiniteStrings:B0chiAutomata
Exercises
6 RegularExpressions
6.1 WhatisaRegularExpression?
6.2 Kleene'sTheorem
6.3 ApplicationsofRegularExpressions
6.4 ManipulatingandSimplifyingRegularExpressions
Exercises
7 RegularGrammars
7.1 DefinitionofaRegularGrammar
7.2 RegularGrammarsandRegularLanguages
Exercises
8 RegularandNonregularLanguages
8.1 HowManyRegularLanguagesAreThere?
8.2 ShowingThataLanguageIsRegular
8.3 SomeImportantClosurePropertiesofRegularLanguages
8.4 ShowingThataLanguageisNotRegular
8.5 ExploitingProblem-SpecificKnowledge
8.6 FunctionsonRegularLanguages
Exercises
9 AlgorithmsandDecisionProceduresforRegular Languages
9.1 FundamentalDecisionProcedures187
9.2 SummaryofAlgorithmsandDecisionProceduresforRegularLanguages
Exercises
10 SummaryandReferences
References
PARTⅢ:CONTEXT-FREELANGUAGESANDPUSHDOWN
AUTOMATA201
11 Context-FreeGrammars
11.1 IntroductiontoRewriteSystemsandGrammars
11.2 Context-FreeGrammarsandLanguages
11.3 DesigningContext-FreeGrammars
11.4 SimplifyingContext-FreeGrammars
11.5 ProvingThataGrammarisCorrect
11.6 DerivationsandParseTrees
11.7 Ambiguity
11.8 NormalForms
11.9 IslandGrammars
11.1 0StochasticContext-FreeGrammars
Exercises
12 PushdownAutomata
12.1 Definitionofa(Nondeterministic)PDA
12.2 DeterministicandNondeterministicPDAs
12.3 EquivalenceofContext-FreeGrammarsandPDAs
12.4 NondeterminismandHalting
12.5 AlternativeEquivalentDefinitionsofaPDA
12.6 AlternativesthatareNotEquivalenttothePDA
Exercises
13 Context-FreeandNoncontext-FreeLanguages
13.1 WhereDotheContext-FreeLanguagesFitintheBigPicture?
13.2 ShowingThataLanguageisContext-Free
13.3 ThePumpingTheoremforContext-FreeLanguages
13.4 SomeImportantClosurePropertiesofContext-FreeLanguages
13.5 DeterministicContext-FreeLanguages
13.6 Ogden'sLemma
13.7 Parikh'sTheorem
13.8 FunctionsonContext-FreeLanguages
Exercises
14 AlgorithmsandDecisionProceduresforContext-Free
Languages
14.1 TheDecidableQuestions
14.2 TheUndecidableQuestions
14.3 SummaryofAlgorithmsandDecisionProceduresforContext-Free
Languages
Exercises
15 Context-FreeParsing
15.1 LexicalAnalysis
15.2 Top-DownParsing
15.3 Bottom-UpParsing
15.4 ParsingNaturalLanguages
Exercises
16 SummaryandReferences
References
PARTIV:TURINGMACHINESANDUNDECIDABILITY
17 TuringMachines364
17.1 Definition,NotationandExamples
17.2 ComputingWithTuringMachines
17.3 AddingMultipleTapesandNondeterminism
17.4 Simulatinga"Real"Computer
17.5 AlternativeTuringMachineDefinitions
17.6 EncodingTuringMachinesasStrings
17.7 TheUniversalTuringMachine
Exercises407
18 TheChurch-TuringThesis
18.1 TheThesis411
18.2 ExamplesofEquivalentFormalisms
Exercises424
19 TheUnsolvabilityoftheHaltingProblem
19.1 TheLanguageHisSemidecidablebutNotDecidable
19.2 SomeImplicationsoftheUndecidabilityofH431
19.3 BacktoTuring,Church,andtheEntscheidungsproblem
Exercises
20 DecidableandSemidecidableLanguages
20.1 D:TheBigPicture
20.2 SD:TheBigPicture
……
PARTⅤ:COMPLEXITY
APPENDICES
……[看更多目录]
序言This book has three goals:
1. To introduce students to the elegant theory that underlies modern computing.
2. To motivate students by showing them that the theory is alive. While much of it has been known since the early days of digital computers (and some of it even longer), the theory continues to inform many of the most important applications that are considered today.
3. To show students how to start looking for ways to exploit the theory in their own work.The core of the book, as a standard textbook, is Parts I through V.They address the first of the stated goals. They contain the theory that is being presented. There is more ma-terial in them than can be covered in a one-semester course. Sections that are marked with a are optional, in the sense that later material does not, for the most part, de-pend on them. The Course Plans section on page xv suggests ways of selecting sections that are appropriate for some typical computer science courses.
文摘插图：
Problems that are not already stated as decision problems. These problems may require results of any type. For these, we must first reformulate the problem as a decision problem and then encode it as a language recognition task.
