本书是关于形式语言、自动机理论和计算复杂性方面的经典之作。书中涵盖了有穷自动机、正则表达式与语言、正则语言的性质、上下文无关文法及上下文无关语言、下推自动机、上下文无关语言的性质、图灵机、不可判定性以及难解问题等内容。本书在定义和证明中使用了很多细节和直观说明,使用图来帮助阐明思想,并包含了大量的难度各异的示例和习题,以便读者确认和加深对内容的理解。
本书适合作为计算机专业高年级本科生及研究生计算理论课程的教材和教学参考书。

出版者的话
专家指导委员会
译者序
前言
第1章 自动机:方法与体验
1.1 为什么研究自动机理论
1.2 形式化证明简介
1.3 其他的证明形式
1.4 归纳证明
1.5 ���动机理论的**概念
1.6 小结
1.7 参考文献
第2章 有穷自动机
2.1 有穷自动机的非形式化描述
2.2 确定型有穷自动机
2.3 非确定型有穷自动机
2.4 应用:文本搜索
2.5 带ε转移的有穷自动机
2.6 小结
2.7 参考文献
第3章 正则表达式与正则语言
第4章 正则语言的性质
第5章 上下文无关文法及上下文无关语言
第6章 下推自动机
第7章 上下文无关语言的性质
第8章 图灵机导引
第9章 不同判定性
第10章 难解问题
第11章 其他问题类
索引

**作者JohnHopcroft和JeffreyUllman在本书第1版出版30多年后再度合作,更新了这本经典著作,作者继续以简洁、直接的方式为读者介绍形式语言、自动机理论和计算复杂性理论。本书被世界许多**大学作为计算理论课程的教材或**教学参考书,它同样适合作为计算机专业高年级本科生及研究生的教材。本书特点:形式化内容较少,使本科生更容易理解;强调理论的现代应用;用大量的图来帮助阐明思想;在定义和证明中增加更多的细节和直观说明;用特殊的文字框提供可能对读者有用的补充材料;用难度各异的大量习题为读者提供更多的挑战;提供PDA和图灵机的图形记号;每章都包含大量的示例和习题,以帮助读者确认和加深对内容的理解。