自动机理论、语言和计算导论（原书第2版）
点击看大图基本信息
- 原书名：Introduction to Automata Theory,Languages,and Computation,Second Edition
- 原出版社： Addison Wesley/Pearson
内容简介回到顶部↑
本书是关于形式语言、自动机理论和计算复杂性方面的经典之作。书中涵盖了有穷自动机、正则表达式与语言、正则语言的性质、上下文无关文法及上下文无关语言、下推自动机、上下文无关语言的性质、图灵机、不可判定性以及难解问题等内容。本书在定义和证明中使用了很多细节和直观说明，使用图来帮助阐明思想，并包含了大量的难度各异的示例和习题，以便读者确认和加深对内容的理解。
本书适合作为计算机专业高年级本科生及研究生计算理论课程的教材和教学参考书。
著名作者johnhopcroft和jeffreyullman在本书第1版出版30多年后再度合作，更新了这本经典著作，作者继续以简洁、直接的方式为读者介绍形式语言、自动机理论和计算复杂性理论。
[font color="#ff0000"]本书被世界许多著名大学作为计算理论课程的教材或推荐教学参考书，它同样适合作为计算机专业高年级本科生及研究生的教材。[/font]
本书特点：
形式化内容较少，使本科生更容易理解
强调理论的现代应用
用大量的图来帮助阐明思想
在定义和证明中增加更多的细节和直观说明
用特殊的文字框提供可能对读者有用的补充材料
用难度各异的大量习题为读者提供更多的挑战
提供pda和图灵机的图形记号
每章都包含大量的示例和习题，以帮助读者确认和加深对内容的理解
本书适合作为计算机专业高年级本科生及研究生计算理论课程的教材和教学参考书。
著名作者johnhopcroft和jeffreyullman在本书第1版出版30多年后再度合作，更新了这本经典著作，作者继续以简洁、直接的方式为读者介绍形式语言、自动机理论和计算复杂性理论。
[font color="#ff0000"]本书被世界许多著名大学作为计算理论课程的教材或推荐教学参考书，它同样适合作为计算机专业高年级本科生及研究生的教材。[/font]
本书特点：
形式化内容较少，使本科生更容易理解
强调理论的现代应用
用大量的图来帮助阐明思想
在定义和证明中增加更多的细节和直观说明
用特殊的文字框提供可能对读者有用的补充材料
用难度各异的大量习题为读者提供更多的挑战
提供pda和图灵机的图形记号
每章都包含大量的示例和习题，以帮助读者确认和加深对内容的理解
作译者回到顶部↑
本书提供作译者介绍
John E．Hopcroft康奈尔大学计算机科学系教授，工程学院Joseph Silbert院长，康奈尔大学工程学院计算机科学系主任。1986年图灵奖获得者。Rajeev Motwani斯坦福大学计算机科学系教授、研究生主管。Jeffrey D．Ullman斯坦福大学计算机科学系Stanford W．Ascherman教授。
.. << 查看详细
.. << 查看详细
目录回到顶部↑
出版者的话
专家指导委员会
译者序
前言
第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章 自动机：方法与体验
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 归纳证明
前言回到顶部↑
在本书1979年的前一版的前言中，Hopcroft和Ullman对下面的事实感到惊异：与1969年写第一本书时的状况相比，自动机的专题已经有了飞速的发展。确实，1979年的书包含了以前的著作中找不到的许多主题，篇幅大约增加了一倍。如果读者把本书与1979年那本书相比就会发现，像20世纪70年代的汽车那样，本书是“外看大，内看小”。这听起来像是退步，但是有理由对此变化感到高兴。
首先，在1979年，自动机和语言理论还是一个活跃的研究领域。那本书的目标是鼓励有数学倾向的学生为这个领域做出新的贡献。今天，几乎不再直接研究自动机理论(而是研究其应用)，因此就几乎没有理由保持1979年那本书的简洁和高度的数学风格。
其次，自动机和语言理论的角色在过去20年里已经发生了改变。在1979年，自动机主要还是研究生水平的专题，那时假定读者是高年级研究生，特别是使用这本书后几章的那些读者。今天，这个专题是本科生课程的主要内容。由于这个原因，本书的内容必须假设对于学生只有很少的预备知识的要求，因此就必须比以前的书提供更多的背景和论证的细节。
环境的第三个变化是，计算机科学在过去20年里已经增长到了几乎无法想像的程度。在1979年，用我们觉得将会经得起下一轮技术考验的材料来填充课程计划，常常是一项挑战；而在今天，却有非常多的子科目在竞争本科生课程的有限空间。
第四，计算机科学已经成为更加职业化的专题，在许多学生中存在着严重的实用主义。我们仍然相信，自动机理论的方方面面是各种新兴学科的重要工具，并且我们相信，无论有多少学生宁愿只学那些最能直接赚钱的技术，在典型的自动机课程中那些理论的和扩展心智的习题还仍然保持其价值。然而，为了保证这个专题在供计算机科学专业学生选择的课程表中持续占有一席之地，我们相信有必要在强调数学的同时也强调应用。因此，我们已经把上一版中许多深奥的主题换成了今天如何使用这些思想的例子。虽然自动机和语言理论对于编译器的应用现在广为人知，以致于这些内容通常包含在编译课程中，但是还有各种较新的用途，包括验证协议的模型验证算法和以上下文无关文法为模式的文本描述语言等。
对于这本书内容既增长又收缩的最后一项解释是，现今能够利用Don Knuth和Les Lamport开发的TEX和LATEX排版系统。特别是后一种系统鼓励“开放”式的排版，让书籍篇幅更大，但更容易阅读。感谢这两个人的努力。
本书用法
本书适合于三年级以上学生的一季度或一学期的课程。在斯坦福大学，我们把这份讲义用在CS154课程中，这是自动机和语言理论的课程。这是一季度的课程，Rajeev和Jeffrey曾经教过。由于授课时间有限，第11章不包括在内，后面一些材料(比如较难的10．4节中的多项式时间归约)也都省略了。本书的网站(参见下面)包括CSl54课程的笔记和教学大纲等材料。
若干年前作者发现，来斯坦福大学的许多研究生都学过一门不包括难解性理论的自动机理论课程。由于斯坦福大学的全体教员相信，对于每一个计算机科学家来说，充分了解这些思想都是重要的，所以就有了另一门课程CSl54N，选这个课的学生可以只学习第8、9和10章。这些学生实际上参加CSl54课程大约后三分之一的学习，来满足CSl54N的要求。即使在今天，作者仍然发现，每季度都有一些学生采取这个选项。由于这样做几乎不要求额外的努力，所以作者推荐这个方法。
预备知识
为了最佳地使用本书，读者应当在以前学过一门关于离散数学(如图、树、逻辑、证明技巧等)的课程。还假设读者学过一些程序设计课程，熟悉普通的数据结构、递归和主要系统组件(如编译器)的作用等。这些预备知识一般应当包含在一、二年级计算机科学课程计划中。
习题
本书包含大量习题，几乎每节都有。把较难的习题或习题部分用叹号标出。最难的习题有两个叹号。
某些习题或习题部分标有星号。对于这些习题，其解答方法可以通过本书的网页获得。这些解答可以公开获得，应当用于自我测试。注意，在少数情况下，习题。要求修改或改编对另一个习题A的解答。如果A的某些部分有解答，那么就应当预期月的对应部分也有解答。
万维网上的支持
本书的主页是
http：//www-db．stanford.edu／~ullman／ialc．html
其中包含带星号的习题的解答、已知的勘误表、后备材料等。作者希望提供所教CSl54课程的每种材料的笔记，包括课后作业、解答和考试等。
致谢
CraigSilverstein关于“如何进行证明”的讲义影响了第1章中的一些材料。对本书手稿的评论和勘误来自ZoeAbrams、GeorgeCandea、HaowenChen、Byong-GunChun、Jeffrey Shallit、BretTaylor、JasonTownsend和ErikUzureau等。非常感谢他们。当然，剩下的错误都由我们负责。
首先，在1979年，自动机和语言理论还是一个活跃的研究领域。那本书的目标是鼓励有数学倾向的学生为这个领域做出新的贡献。今天，几乎不再直接研究自动机理论(而是研究其应用)，因此就几乎没有理由保持1979年那本书的简洁和高度的数学风格。
其次，自动机和语言理论的角色在过去20年里已经发生了改变。在1979年，自动机主要还是研究生水平的专题，那时假定读者是高年级研究生，特别是使用这本书后几章的那些读者。今天，这个专题是本科生课程的主要内容。由于这个原因，本书的内容必须假设对于学生只有很少的预备知识的要求，因此就必须比以前的书提供更多的背景和论证的细节。
环境的第三个变化是，计算机科学在过去20年里已经增长到了几乎无法想像的程度。在1979年，用我们觉得将会经得起下一轮技术考验的材料来填充课程计划，常常是一项挑战；而在今天，却有非常多的子科目在竞争本科生课程的有限空间。
第四，计算机科学已经成为更加职业化的专题，在许多学生中存在着严重的实用主义。我们仍然相信，自动机理论的方方面面是各种新兴学科的重要工具，并且我们相信，无论有多少学生宁愿只学那些最能直接赚钱的技术，在典型的自动机课程中那些理论的和扩展心智的习题还仍然保持其价值。然而，为了保证这个专题在供计算机科学专业学生选择的课程表中持续占有一席之地，我们相信有必要在强调数学的同时也强调应用。因此，我们已经把上一版中许多深奥的主题换成了今天如何使用这些思想的例子。虽然自动机和语言理论对于编译器的应用现在广为人知，以致于这些内容通常包含在编译课程中，但是还有各种较新的用途，包括验证协议的模型验证算法和以上下文无关文法为模式的文本描述语言等。
对于这本书内容既增长又收缩的最后一项解释是，现今能够利用Don Knuth和Les Lamport开发的TEX和LATEX排版系统。特别是后一种系统鼓励“开放”式的排版，让书籍篇幅更大，但更容易阅读。感谢这两个人的努力。
本书用法
本书适合于三年级以上学生的一季度或一学期的课程。在斯坦福大学，我们把这份讲义用在CS154课程中，这是自动机和语言理论的课程。这是一季度的课程，Rajeev和Jeffrey曾经教过。由于授课时间有限，第11章不包括在内，后面一些材料(比如较难的10．4节中的多项式时间归约)也都省略了。本书的网站(参见下面)包括CSl54课程的笔记和教学大纲等材料。
若干年前作者发现，来斯坦福大学的许多研究生都学过一门不包括难解性理论的自动机理论课程。由于斯坦福大学的全体教员相信，对于每一个计算机科学家来说，充分了解这些思想都是重要的，所以就有了另一门课程CSl54N，选这个课的学生可以只学习第8、9和10章。这些学生实际上参加CSl54课程大约后三分之一的学习，来满足CSl54N的要求。即使在今天，作者仍然发现，每季度都有一些学生采取这个选项。由于这样做几乎不要求额外的努力，所以作者推荐这个方法。
预备知识
为了最佳地使用本书，读者应当在以前学过一门关于离散数学(如图、树、逻辑、证明技巧等)的课程。还假设读者学过一些程序设计课程，熟悉普通的数据结构、递归和主要系统组件(如编译器)的作用等。这些预备知识一般应当包含在一、二年级计算机科学课程计划中。
习题
本书包含大量习题，几乎每节都有。把较难的习题或习题部分用叹号标出。最难的习题有两个叹号。
某些习题或习题部分标有星号。对于这些习题，其解答方法可以通过本书的网页获得。这些解答可以公开获得，应当用于自我测试。注意，在少数情况下，习题。要求修改或改编对另一个习题A的解答。如果A的某些部分有解答，那么就应当预期月的对应部分也有解答。
万维网上的支持
本书的主页是
http：//www-db．stanford.edu／~ullman／ialc．html
其中包含带星号的习题的解答、已知的勘误表、后备材料等。作者希望提供所教CSl54课程的每种材料的笔记，包括课后作业、解答和考试等。
致谢
CraigSilverstein关于“如何进行证明”的讲义影响了第1章中的一些材料。对本书手稿的评论和勘误来自ZoeAbrams、GeorgeCandea、HaowenChen、Byong-GunChun、Jeffrey Shallit、BretTaylor、JasonTownsend和ErikUzureau等。非常感谢他们。当然，剩下的错误都由我们负责。
加载中...
