自动机理论、语言和计算导论(原书第3版)

　　本书是关于形式语言、自动机理论和计算复杂性方面的经典之作，是国际上得到广泛认可的计算机理论和计算机工程专业的优秀教材。书中涵盖了有穷自动机、正则表达式与语言、正则语言的性质、上下文无关文法及上下文无关语言、下推自动机、上下文无关语言的性质、图灵机、不可判定性以及难解问题等内容。本书注重定义、定理的准确性和严格性，注重学生形式化和严格的数学推理能力的培养，同时在定义和证明中运用直观的方法说明抽象概念，借助许多图表帮助传达思想，并包含大量难度各异的示例和习题，便于读者加深对内容的理解。
　　 本书适合作为计算机专业高年级本科生及研究生计算理论课程的教材和教学参考书。

出版者的话
译者序
前言
第1章 自动机：方法与体验
　1.1 为什么研究自动机理论
　　1.1.1 有穷自动机简介
　　1.1.2 结构表示法
　　1.1.3 自动机与复杂性
　1.2 形式化证明简介
　　1.2.1 演绎证明
　　1.2.2 求助于定义
　　1.2.3 其他定理形式
　　1.2.4 表面上不是“如果-则”命题的定理
　1.3 其他的证明形式
　　1.3.1 证明集合等价性
　　1.3.2 逆否命题
　　1.3.3 反证法
　　1.3.4 反例
　1.4 归纳证明
　　1.4.1 整数上的归纳法

　　理论计算机科学是推动计算机技术向前发展的强大动力。自动机、形式语言、可计算性和相关方面内容构成的计算理论，是理论计算机科学的基础内容之一。学习、研究这些内容，不仅为进一步学习、研究理论计算机科学所必需，而且对增强形式化能力和推理能力有重要作用，这些能力对从事计算机技术中的软件形式化等研究，是不可缺少的。.
　　本书是由John E. Hopcroft、Rajeev Motwani和Jeffrey D. Ullman三位计算机学者合作编写的，是最著名的理论计算机科学著作之一，是世界各国广泛采用的计算机理论专业和计算计工程专业的优秀教材之一。它主要介绍形式语言、自动机、可计算性和相关方面内容。它特别注意定义、定理的准确性和严格性，这有利于培养学生形式化和严格的数学推理的能力。本书第1版于1979年发行。它的第3版有一个新的特色，那就是增加了一套由Gradiance公司开发的在线作业帮助系统。教师可以利用它给学生安排课后作业，或者给那些没有选课的学生提供一个特殊的综合课程（不是由老师申请开设的课程），使得他们可以利用这些课后作业作为练习和指导。然而遗憾的是，Gradiance在线作业系统只适用于购买原版教材的北美地区学生，中国学生还不能使用这个系统，因此，我们在翻译第3版的过程中，对涉及Gradiance系统的内容进行了删减。..
　　引进国外的优秀计算机教材，无疑会对我国的计算机教育事业的发展起积极推动作用，也是与世界接轨、建立世界一流大学不可缺少的条件。我们把本书介绍给国内从事计算机教育事业的同行们，以供参考。
　　这个译本是根据原书第3版翻译的。参加本书翻译的有：孙家同志，负责各章译稿的详细修改和全书的统稿；刘明浩同志，负责第1～3章及前言、目录的翻译；孙自然同志，负责第4、5章的翻译；王啸吟同志，负责第6、7章的翻译；王华同志，负责第8、9章的翻译；侯姗姗同志，负责第10、11章及索引的翻译。为了与本书第2版中译本用的名词、术语保持统一，在翻译过程中我们参考了由刘田、姜晖和王捍贫同志完成的本书第2版中译本。
　　由于我们的能力有限，难免有不当之处，敬请读者不吝赐教。 ...
　　译者
　　2008年3月
　　

　　在本书1979年出版的前一版的前言中，Hopcroft和Ullman对于下面的事实感到惊诧不已：与1969年他们写第一本书时的情形相比，自动机这一专题已经有了突破性地发展。的确，1979年版的书中包含许多在以前的著作中找不到的主题，篇幅增加了大约一倍。如果读者有兴趣把本书与1979年版的那本书做个比较就会发现，正如20世纪70年代的汽车那样，本书是“外看大，内看小”。这表面看起来像是退步，但是我们有理由对此变化感到高兴。.
　　首先，在1979年，自动机和语言理论还是一个比较活跃的研究领域。那本书的主要目的是鼓励擅长数学的学生为这个领域做出新的贡献。然而今天，直接针对自动机理论的研究几乎已经销声匿迹（相反，更多的是对其应用的研究），因此也就没有理由继续保持1979年那本书的简洁和高度数学化的风格。
　　其次，在过去的20年里，自动机和语言理论的角色已经发生了很大的变化。在1979年，自动机还主要是研究生水平的专题，那时我们假定的读者是高年级研究生，特别是使用这本书后几章的那些读者。然而到了今天，它已经成为本科生课程的主要内容。正是基于这个原因，本书在编排时必须假定对于读者只有很少的预备知识的要求，因此必须比前一版本的书提供更多的背景知识介绍和论证的细节。
　　环境的第三个变化是，计算机科学在过去的30年里已经发展到了几乎无法想像的程度。在1979年，我们觉得可能会经受得起下一轮技术考验的材料太少了，以致于排满课程计划都很难；然而今天，却有非常多的子科目在竞争本科生课程的有限空间。
　　第四，计算机科学如今已经发展成为更加职业化的科目，在许多学习它的学生中存在着严重的实用主义倾向。但我们仍然相信，自动机理论的方方面面是各种新兴学科的重要工具，并且我们相信，无论学生多么倾向于只去学习那些最能直接赚钱的技术，但在典型的自动机课程中，那些理论的和有利于拓宽思维的习题依然可以保持其价值。然而，为了保证这个科目在计算机科学专业学生的课程表中继续占有一席之地，我们相信有必要在强调数学理论的同时也强调应用。因此，我们把上一版中许多比较深奥的主题换成了今天如何使用这些思想的例子。虽然自动机和语言理论在众多编译器上的应用如今已经广为人知，以至于这些内容通常已经包含在介绍编译技术的课程中，但是还存在一些较新的用途，包括用来验证协议的模型验证算法以及采用与上下文无关文法的模式的文本描述语言等，本书对此进行了补充说明。
　　对于本书内容增减的最后一项解释是，如今我们能够充分利用Don Knuth和Les Lamport开发的TEX和LATEX排版系统的优点。特别是后一种系统，它鼓励“开放”式的排版，让书籍篇幅更大，但更容易阅读。感谢这两个人的努力为本书出版发行作出的贡献。
　　本书用法
　　本书适合于本科三年级以上学生的一季度或一学期的课程。在斯坦福大学，我们把这份讲义用在CS154课程中，这是自动机和语言理论的课程。这是门一季度的课程，Rajeev和Jeffrey都曾经教过。由于授课时间有限，第11章不包括在授课范围以内，后面一些材料（比如较难的10.4节中的多项式时间归约等内容）也都省略了。本书的网站（参见下面）包括CS154课程的笔记和教学大纲等材料。..
　　几年前我们发现，许多进入斯坦福大学的研究生都学过一门不包括难解性理论的自动机理论课程。由于斯坦福大学的全体教员相信，对于每一位计算机科学家来说，仅仅停留在知道“NP完全意味着需要花费很长时间”这一层面是远远不够的，充分了解这些思想是十分必要的，所以就有了另外一门课程CS154N，选这个课的学生可以只学习第8、9和10章。他们实际上学习CS154课程大约后三分之一部分的内容，由此来满足CS154N课程的要求。即使在今天，我们仍然发现，每个季度都有一些学生采取这种优化的课程选项。由于这样做几乎不需要额外的努力，所以我们推荐使用这种方法。
　　预备知识
　　为了最好地使用本书，读者应当在这以前学过一门关于离散数学（如图、树、逻辑、证明技巧等）的课程。我们还假设读者学过一些有关程序设计的课程，熟悉常见的数据结构、递归和主要系统组件（如编译器）的作用等。这些预备知识一般应当包含在大学一、二年级计算机科学课程计划中。
　　习题
　　本书中包含大量的习题，几乎每个章节都有。我们将较难的习题或其中的某一部分用单个叹号标出，最难的则用两个叹号标出。
　　某些习题或其中的某一部分标有星号。对于这部分习题，其解答方法可以通过本书的网页获得。这些解答可以公开获得，只限于进行自我检查。需要注意的一点是，在少数情况下，习题B要求修改或改编对另一个习题A的解答。如果A的某些部分有解答，那么你就应当预期B的对应部分也应当有解答。
　　Gradiance 在线作业
　　本书第3版有一个新的特色，即增加了一套由Gradiance公司开发的在线作业伴随系统。教师可以利用它给学生安排课后作业，或者给那些没有选课的学生提供一个特殊的综合课程（不是由老师申请开设的课程），使得他们可以利用这些课后作业作为练习和指导。Gradiance系统所提供的问题和普通问题的形式一样，但会对你提交的解决方案进行检查。如果你提交的答案不正确，系统将会提供一些针对性的建议或反馈意见，以帮助纠正你的解决方案。只要你的老师允许，就可以重复尝试，直到达到一个满意的分数为止。
　　所有在北美地区购买这本书第3版的读者，都将自动获得这项Gradiance在线作业服务的授权。更多的信息，请访问Addison-Wesley网站 www.aw.com/gradiance 或者发邮件给 computing@aw.com 。
　　万维网上的支持
　　本书的主页是
　　http://www-db.stanford.edu/~ullman/ialc.html

　　第1章自动机：方法与体验
　　 自动机理论研究抽象计算装置或“机器”。在20世纪30年代计算机出现之前，图灵研究过一种抽象机器，这种机器具备了今天计算机的所有能力，至少在计算能力上是这样的。图灵的目标是精确地描述一条界线，这条界线区分计算机能做什么和不能做什么；图灵的结论不仅适用于抽象的图灵机，也适用于今天的真实机器。
　　 在20世纪40和50年代，许多研究者研究过更简单类型的机器，今天称为“有穷自动机”。起初建议用这些自动机来为人脑功能建立模型，后来发现这些自动机对于1.1节提到的各种其他目的也极为有用。在20世纪50年代后期，语言学家乔姆斯基（N.chomsky）开始研究形式“文法”。尽管这些文法不是严格意义上的机器，但与抽象自动机有密切关系，而且目前是一些重要软件部件（包括部分编译器在内）的基础。
　　 在1969年，库克（s.C00k）扩展了图灵对什么能被计算和什么不能被计算的研究。库克设法分离出了两类问题：一类是计算机能有效解决的；另一类是计算机理论上能解决，但实际上要花费太长时间，以致除了非常小的问题实例以外，计算机是毫无用处的。后一类问题称为“难解的”或“NP-难的”。计算机硬件一直遵循着计算速度呈指数增长的规律（摩尔定律），但这也不太可能显著地影响解决难解问题大实例的能力。
　　所有这些理论进展都直接影响了计算机科学家今天的工作。有些概念，比如有穷自动机和某些类型的形式文法，用于设计和构造重要类型的软件。另一些概念，比如图灵机，则帮助我厂n们理解能期待软件做什么。特别是，难解问题的理论允许推断是否有可能“正面”处理一个问题，编写解决这个问题的程序（因为这个问题不属于难解的一类），或者是否需要找到某种方法来迂回处理这个难解的问题：找近似算法、用启发式算法或者用某种其他方法来限制程序解决这个问题所花费的时间。
　　……