自动机理论与应用
2009-11
清华大学出版社
里奇
1099
无
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.
本书阐述了计算科学的优美理论基础，通过演示计算理论在现代硬件和软件系统设计中的影响，把理论知识带到了现实实践之中。本书介绍了关键概念的应用，为读者在实际工作中使用计算理论提供实际指导。本书讨论的应用包括：程序设计语言、编译器、网络技术、自然语言处理、人工智能、计算生物学、安全性、博弈、商业规则建模、标识语言、Web搜索等。本书既适合作为自动机理论课程的教程，也是相关专业人员的重要参考用书。
作者：(美国)里奇(Rich.E.)
PrefaceAcknowledgmentsCreditsPART Ⅰ INTRODUCTION 1 Why study the Theory of Computation? 2 Languages and Strings 3 The Big Picture: A Language Hierarchy 4 ComputationPART Ⅱ FINITE STATE MACHINES AND REGULAR LANGUAGES 5 Finite State Machines 6 Regular Expressions 7 Regular Grammars 8 Regular and Nonregular Languages 9 Algorithms and Decision Procedures for Regualr Languages 10 Summary and ReferencePART Ⅲ CONTEXT-FREE LANGUAGES AND PUSHDOWN AUTOMATA 11 Context-Free Grammars 12 Rushdown Automata 13 Context-Free and Noncontext-Free Languages 14 Algorithms and Decision procedures for Context-Free Languages 15 Context-Free Parsing 16 Summary and referencesPART Ⅳ TURING MACHINES AND UNDECIDABILITY 17 Turing Machines 18 The Church-Turing Thesis 19 The Church-Turing Thesis 20 Decidable and Semidecidable Languages 21 Decidability and Undecidability Proofs……PART Ⅴ COMPLEXITYAPPENDICESAPPENDICES G-Q: APPLICATIONS
插图：3.2 The Power of EncodingThe question that we are going to ask, "Is w in L？" may seem, at first glance, way toolimited to be useful. What about problems like multiplying numbers, sorting lists, andretrieving values from a database？ And what about real problems like air traffic controlor inventory management？ Can our theory tell us anything interesting about them？ The answer is yes and the key is encoding. With an appropriate encoding, otherkinds of problems can be recast as the problem of deciding whether a string is in a lan-guage. We will show some examples to illustrate this idea. We will divide the examplesinto two categories:Problems that are already stated as decision problems. For these, all we need to do is to encode the inputs as strings and then define a language that contains exactly the set of inputs for which the desired answer is yes.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.
《自动机理论与应用(影印版)》：大学计算机教育国外著名教材系列
无
挺好用的，相对原版便宜不少。
无论价格高低，无论书薄厚，卓越一如既往地用那么薄的塑料袋装，真的很无语。书的内容不错，就是用的纸张实在是不敢恭维，要是没有防伪标签估计所有人都会认为是D版的。