自动机理论、语言和计算导论(原书第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 归纳证明
<< 查看详细目录

【译者序】

理论计算机科学是推动计算机技术向前发展的强大动力。自动机、形式语言、可计算性和相关方面内容构成的计算理论，是理论计算机科学的基础内容之一。学习、研究这些内容，不仅为进一步学习、研究理论计算机科学所必需，而且对增强形式化能力和推理能力有重要作用，这些能力对从事计算机技术中的软件形式化等研究，是不可缺少的。.
本书是由John E. Hopcroft、Rajeev Motwani和Jeffrey D. Ullman三位计算机学者合作编写的，是最著名的理论计算机科学著作之一，是世界各国广泛采用的计算机理论专业和计算计工程专业的优秀教材之一。它主要介绍形式语言、自动机、可计算性和相关方面内容。它特别注意定义、定理.. << 查看译者序

【前言】

在本书1979年出版的前一版的前言中，Hopcroft和Ullman对于下面的事实感到惊诧不已：与1969年他们写第一本书时的情形相比，自动机这一专题已经有了突破性地发展。的确，1979年版的书中包含许多在以前的著作中找不到的主题，篇幅增加了大约一倍。如果读者有兴趣把本书与1979年版的那本书做个比较就会发现，正如20世纪70年代的汽车那样，本书是“外看大，内看小”。这表面看起来像是退步，但是我们有理由对此变化感到高兴。.
首先，在1979年，自动机和语言理论还是一个比较活跃的研究领域。那本书的主要目的是鼓励擅长数学的学生为这个领域做出新的贡献。然而今天，直接针对自动机理论的研究几乎已经销声匿迹（.. << 查看前言

【书摘】

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

【免费试读】

　电子书Web试读版：试读本书　全部品种