自动机理论、语言和计算导论

出版者的话

译者序

前言

第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整数上的归纳法

1.4.2更一般形式的整数归纳法

1.4.3结构归纳法

1.4.4互归纳法

1.5自动机理论的中心概念

1.5.1字母表

1.5.2串

1.5.3语言

1.5.4问题

1.6小结

1.7参考文献

第2章有穷自动机

第3章正则表达式与正则语言

第4章正则语言的性质

第5章上下文无关文法及上下文无关语言

第6章下推自动机

第7章上下文无关语言的性质

第8章图灵机导引

第9章不可判定性

第10章难解问题

第11章其他问题类

　　本书是由JohnE.Hopcroft、RajeevMotwani和JeffreyD.Ullman三位计算机学者合作编写的，是最著名的理论计算机科学著作之一，是世界各国广泛采用的计算机理论专业和计算计工程专业的优秀教材之一。书中涵盖了有穷自动机、正则表达式与语言、正则语言的性质、上下文无关文法及上下文无关语言、下推自动机、上下文无关语言的性质、图灵机、不可判定性以及难解问题等内容。本书适合作为国内高校计算机高年级本科生或研究生的教材，还可供从事理论计算工作的研究人员参考。　　本书是关于形式语言、自动机理论和计算复杂性方面的经典之作，是国际上得到广泛认可的计算机理论和计算机工程专业的优秀教材。书中涵盖了有穷自动机、正则表达式与语言、正则语言的性质、上下文无关文法及上下文无关语言、下推自动机、上下文无关语言的性质、图灵机、不可判定性以及难解问题等内容。本书注重定义、定理的准确性和严格性，注重学生形式化和严格的数学推理能力的培养，同时在定义和证明中运用直观的方法说明抽象概念，借助许多图表帮助传达思想，并包含大量难度各异的示例和习题，便于读者加深对内容的理解。　　本书适合作为计算机专业高年级本科生及研究生计算理论课程的教材和教学参考书。【作者简介】　　JohnE.Hopcroft于斯坦福大学获得博士学位。现为康奈尔大学计算机科学系教授。1994年到2001年，任康奈尔大学工程学院院长。他是1986年图灵奖获得者。他的研究兴趣集中在计算理论方面。尤其是算法分析、自动机理论等。