自动机理论、语言和计算导论(英文版.第3版)

出版时间：2007-9  出版社：机械工业  作者：John E. Hopcroft,Rajeev Motwani,Jeffrey D. Ullman  页数：535  
Tag标签：无  

内容概要

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

作者简介

John E.Hopcroft  于斯坦福大学获得博士学位，现为康奈尔大学计算机科学系教授。1994年到2001年，任康奈尔大学工程学院院长。他是1986年图灵奖获得者。他的研究兴趣集中在计算理论方面，尤其是算法分析、自动机理论等。

书籍目录

1 Automata: The Methods and the Madness　1.1  Why Study Automata Theory?　　1.1.1  Introduction to Finite Automata　　1.1.2  Structural Representations　　1.1.3  Automata and Complexity　1.2  Introduction to Formal Proof　　1.2.1  Deductive Proofs　　1.2.2  Reduction to Definitions　　1.2.3  Other Theorem Forms　　1.2.4  Theorems That Appear Not to Be If-Then Statements　1.3  Additional Forms of Proof　　1.3.1  Proving Equivalences About Sets　　1.3.2  The Contrapositive　　1.3.3  Proof by Contradiction　　1.3.4  Counterexamples　1.4  Inductive Proofs　　1.4.1  Inductions on Integers　　1.4.2  More General Forms of Integer Inductions　　1.4.3  Structural Inductions　　1.4.4  Mutual Inductions　1.5  The Central Concepts of Automata Theory　　1.5.1  Alphabets　　1.5.2 , Strings　　1.5.3  Languages　　1.5.4  Problems　1.6  Summary of Chapter 1　1.7  Gradiance Problems for Chapter 1　1.8  References for Chapter 12 Finite Automata　2.1  An Informal Picture of Finite Automata    2.1.1  The Ground Rules　　2.1.2  The Protocol　　2.1.3  Enabling the Automata to Ignore Actions　　2.1.4  The Entire System as an Automaton　　2.1.5  Using the Product Automaton to Validate the Protocol　2.2  Deterministic Finite Automata　　2.2.1  Definition of a Deterministic Finite Automaton　　2.2.2  How a DFA Processes Strings　　2.2.3  Simpler Notations for DFA's　　2.2.4  Extending the Transition Function to Strings　　2.2.5  The Language of a DFA　　2.2.6  Exercises for Section 2.2　2.3  Nondeterministic Finite Automata　　2.3.1  An Informal View of Nondeterministic Finite Automata　　2.3.2  Definition of Nondeterministic Finite Automata　　2.3.3  The Extended Transition Function　　2.3.4  The Language of an NFA　　2.3.5  Equivalence of Deterministic and Nondeterministic Finite Automata　　2.3.6  A Bad Case for the Subset Construction　　2.3.7  Exercises for Section 2.3  2.4  An Application: Text Search　　2.4.1  Finding Strings in Text　　2.4.2  Nondeterministic Finite Automata for Text Search　　2.4.3  A DFA to Recognize a Set of Keywords　　2.4.4  Exercises for Section 2.4  2.5  Finite Automata With Epsilon-Transitions　　2.5.1  Uses of e-Transitions　　2.5.2  The Formal Notation for an c-NFA　　2.5.3  Epsilon-Closures　　2.5.4  Extended Transitions and Languages for c-NFA's　　2.5.5  Eliminating e-Transitions　　2.5.6  Exercises for Section 2.5　2.6  Summary of Chapter 2　2.7  Gradiance Problems for Chapter 2　2.8  References for Chapter 23 Regular Expressions and Languages　3.1  Regular Expressions　　3.1.1  The Operators of Regular Expressions　　3.1.2  Building Regular Expressions　　3.1.3  Precedence of Regular-Expression Operators　　3.1.4  Exercises for Section 3.1　3.2  Finite Automata and Regular Expressions　　3.2.1  From DFA's to Regular Expressions　　3.2.2  Converting DFA's to Regular Expressions by Eliminating States……4 Properties kf Regular Languages5 Context-Free Grammars and Languages6 Pushdown Automata7 Properties of Context-Free Languages8 Introduction to Turing Machines9 Undecidability10 Intractable Problems11 Additional Classes of ProblemsIndex

用户评论 (总计35条)

•   T大贵系形式语言与自动机教材~
•   学习自动机理论的很好的书籍，强烈推荐中英合买
•   听说是清华大学计算机系教材~就买来看了看，结果被其里面通俗易懂的语言和其原理深深的吸引，欲罢不能，不似以前的某些教科书，讲的知识过于沉闷和拘于形式。这本书常常会联系一些生活中的例子来说明某些异常难懂的理论。或许，这是美国大学教材和中国的不同吧~
•   学计算机专业的可以看看这本书，很多人本科四年念完计算机，甚至加上三年研究生，对计算机还没有一个系统的理解，很多课程也没能有效的结合到一起，最后也只是一个个散落的点。
•   经典著作，书的质量很好，支持正版
•   书发的挺快，完好
•   看着作者来历不错的……具体书怎么样还没看，等看到了再说……
•   可以收藏，长期保存
•   英文版的，非常值得去读。Hopcroft是这方面的大师。
•   纸张一般，发货速度挺快，，英文的，还没看。。。
•   这印刷质量太差了，整本书都印歪了，印的也不清楚，很模糊，纸的质量也是不好。
•   书的纸张很薄，字迹不是特别清晰
•   适合入门且评价不错，价格公道送货迅速
•   不错，内容很好，印刷也很好
•   无论是绿龙, 红龙还是最近的紫龙…打龙必备!
•   很不错的书，正在看。里面的题目难度也比较合适。
•   不得不看，但作为教材还是不错的
•   这本我看了好几遍，是一本非常的书，我推荐给大家
•   书是经典，但印刷质量不好，纸质较差。
•   这本书的质量不错，而且是最新版本的，希望以后多引进这方面的书。
•   　　 读《Introduction to Automata Theory、Languages and Computation》（自动机理论、语言和计算导论）时候。遇到了一个问题。这个问题是这样的。
  　　
  　　 书在讲到P与NP时，首先要给“时间复杂性”下一个定义。那就是，对于一台图灵机，首先要求它不论接受与否总会停机（也就是说它是一个“算法”），并且，对于全体长度为n的输入，它运行的步数不超过T(n)。T(n)是n的多项式函数。这样的话就说这台图灵机的时间复杂度是T(n)。它接受的那个语言属于P。
  　　
  　　 但在432页的框中，作者又说道，这个定义可以改一下：不必要求图灵机对于任何输入总停机，只要求它在”接受“的情况下停机，并且是在T(n)步之内，就可以了。因为，既然存在这个”接受“情况下的步数上限T(n)，那么我们可以构造一台新图灵机：一开始这台新图灵机先数一下输入有多长，也就是n，然后计算T(n)，把这个上限记下来。之后新图灵机模拟原来那台图灵机，每模拟一步计数加一。如果新图灵机没有进入接受状态，但是步数超了上限T(n)。由于原来那台机器只要”接受“，就一定会在T(n)步之内就进入接受状态并停机了。如此看来，现在已经超了上限，原来那台机器不可能”接受“了，那么这台新机器就可以停机了（但不进入接受状态，也就是说，停机并拒绝输入字符串）。这样就构造了一台无论如何总会停机的图灵机。这台新机器用了附加的带进行计数和草稿。随后把多带图灵机转成单带图灵机时，运行时间会增长，但是增长是多项式的。于是新机器是一台多项式时间内总会停机的机器。这就说明了上面说的两种定义其实是等价的。
  　　
  　　 这时候我忽然想到一个问题。上面说对于长为n的输入在T(n)内”接受“的图灵机，都可以修改构造出一台永远停机的图灵机。那么对于一般的图灵机呢？对于任何图灵机，长度为n的输入只有有有限个，其中它”接受“的输入自然也只有有限个，”接受“的情况下图灵机总会停机。也就是说，对于所有长度为n的输入，图灵机”接受“的话，总存在一个的最大步数T(n)。T(n)是一个自然数到自然数的映射：任何一个n（输入串的长度），都对应着一个T(n)（就是某台图灵机对于所有长度n的输入，"接受”的情况下运行的最大步数）。这个映射也许不能写成一个方程（一个等式），但它确实是一个映射。那么就存在一个方程 f(n)，使得对于所有n，f(n) >= T(n)。这样用上面那段里，也就是书中432页框里的方法，不是就可以构造一台永远停机的图灵机了么？
  　　
  　　 如果上面说的成立的话，那么任何图灵机都可以构造一台接受相同语言的总停机的图灵机。也就是任何可被图灵机接受的语言，都可以构造一台永远停机的图灵机接受它。也就是任何递归可枚举语言都是递归语言。通用语言Lu是可判定的。对角线语言Ld是图灵机可接受的。可是这些都是不可能的。
  　　
  　　 上面说的构造法必有错误。后来我想出来错在哪儿了。就错在：“那么就存在一个方程 f(n)，使得对于所有n，f(n) >= T(n)” 上。这个问题就变成了：对于任意一个n -> n的映射T(n)，是否存在一个 f(n)，使得对于所有n，f(n) >= T(n)。注意 f(n)是可以写成一个等式的，而T(n)有可能写不成，而只能写成一对一对的映射，比如，T(1)=5,T(2)=888,T(3)=1000,T(4)=1,......无穷无尽写下去。如果存在，上面那些矛盾就都存在。下面可以证明，这样的f(n)，并不一定存在。
  　　
  　　 因为，用那种构造法，需要从n计算出上限T(n)，这个计算也是由这个新图灵机的一部分完成的。这个“部分”可以看做是一个子程序、子图灵机。它单拎出来也是一台图灵机。也就是我们说的那个在所有n上大于等于T(n)、好被我们用来计算图灵机运行步数上限的f(n)，必得是一个图灵机能计算的函数。这样我这台新图灵机才有能力根据输入长度计算这个上限f(n)。后面说的计数、超上限就停机等等才能做到。但是是否对于任何映射T(n)，都能找到一个“盖过”它的、可以被图灵机计算的f(n)呢？
  　　
  　　 不能！理由如下：全体图灵机是可列的，其中可以用来算f(n)的图灵机也是可列的（可列集的子集还可列），那么我们画一个矩阵:
  　　
  　　
  　　—————— 1——2—— 3—— 4—— 5—— 6——7——8 ......
  　　 图灵机1—— 23
  　　 图灵机2—— —— 43
  　　 图灵机3—— —— —— —45—— —— —— 178
  　　 图灵机4—— —— —— —— —65
  　　 图灵机5—— —— —— —— —— ——76
  　　 图灵机6—— —— —— —— —— —— —— 78
  　　 ......
  　　
  　　（请无视那些 —— 它们只是为了把格式撑开）
  　　
  　　 这个矩阵，横向上涵盖所有自然数，纵向上涵盖所有算各种f(n)的图灵机（这些图灵机可列）。每一个元素，就是该行的图灵机把该列的那个自然数算成什么。比如图中看到：图灵机3，它计算的函数就叫f3(n)吧，把6算成178，f3(6)=178。这个矩阵对角线上的元素，就是n号图灵机把n算成什么值。
  　　
  　　 利用对角线法，构造一个映射T(n)，T(n)把每个n，映射为比n行n列对角线交点上那个值大1的值。比如T(3)=46（比 3 行 3 列上的 45 大 1）。这个映射T(n)是存在的（因为我们构造出它来了）。但是这个映射，找不到任何图灵机可计算的f(n)，使得在所有n上，f(n)>=T(n)。因为对于每一个f(n)，我的T(n)总在一个n上比f(n)大（对角线上那些值）就是说是：“那么就存在一个方程 f(n)，使得对于所有n，f(n) >= T(n)”是不对的。准确点说是对于我们如此构造的T(n)，不存在一个图灵机可计算的 f(n)，使得对于所有n，f(n)都大于等于T(n)。
  　　
  　　 不是所有的图灵机都可以构造一台与它接受同样语言的、且永远停机的图灵机。那些矛盾的结论就都出不来了。
•   　　书中通过将 3SAT 问题多项式时间规约到独立集问题。证明了独立集问题是NP完全的。
  　　
  　　
  　　但他的独立集问题IS，是这么表述的：
  　　
  　　给定一个无向图(n个顶点)和一个数k，问这个图存不存在k个顶点的独立集。
  　　
  　　这个问题是P的。因为，对于题面中给定的k，从全部n个定点中选出k个顶点的子集的个数是 c = C(n,k) = n! / (k!*(n-k)!)。这个数是n的多项式。挨个考察这 c 个顶点子集是否独立，每次考察需要多项式时间。一共有多项式次考察，每次考察又是多项式时间，于是这个算法总时间是多项式的。
  　　
  　　也就是说，IS问题，像书中那么表述的话，是P不是NP，自然也不是NP-Complete。
  　　
  　　其实书中没有将3SAT问题归约成像上面陈述的那种IS问题。问题就在于上面陈述中的k，是一个与n无关的量。
  　　
  　　书中用3SAT问题中的那个 3CNF构造出来那个图，然后找它的独立集，要求要找的独立集的定点数不是一个与n无关的k，而是k=n/3。3CNF的每个文字一个顶点，每个字句三个顶点，出来的那个图，要想判断原来那个3CNF是否可满足，就要看存不存在k=n/3个顶点的独立集。
  　　
  　　如果k是n/3，那么按上面说的那个算法，需要遍历考察的子集数就是 C(n,n/3)了，这就不是多项式，而是指数了。
  　　
  　　给作者（Ullman）写了信。他说这问题早就发现了。
•   　　建议大家还是直接读原著吧，不要看翻译的了。
  　　
  　　今天看的时候，发现一句话很费解，特意对比了一下：
  　　翻译版本的41页第二段：“重要的是注意，子集构造是这样一个例子：说明如何……”
  　　
  　　看了一下原文是这样写的（原书第二版61页第一段）：“It is important fot us to observe the subset construction as an example of how one formally……”
  　　
  　　这种翻译方法真是惊天地，泣鬼神啊。
  　　正确的应该翻译为：“重要的是（我们）应该将子集构造看成是如何形式化地……的一个实例。”
  　　observe something as something，这样的句式都看不出来吗？
•   lz你的名字难道出自“觉今是而作非”么
•   作-->昨
•   是啊 ： ）
•   哥果然有文化
•   他是说已经出过勘误表了, 还是在后续印次里纠正了?
•   没有说。这影印版是第三版，好像没有更新的版本。网上勘误表里也没有，我写信前查过。
•   版次往往有N次印刷, 会在后续刷次勘误, 我在另一本Sedgewick的Algorithms, 4E有过经验
  不过既然勘误表没有, 那后续印次纠正的可能不大
•   这第2版的中文版的确很差。不过第三版换孙家骕翻译了，应该好很多吧
•   不幸的是，第三版译版还是很差，感觉都像机翻的，前后翻译风格还不一致= =||
•   所以推荐大家还是看英文吧。
•   我去！手滑误点“关键情节泄露”不能取消么= =？
•   确实翻译得很差, 看了一会儿很后悔买了书. 比如105页的"两个正则语言的两个描述是否其实定义相同语言的问题涉及到相当可观的智力技巧". 不知道多少人看了这句话会放弃中文版.