Elaine Rich编著的《自动机理论与应用》阐述了计算科学的优美理论基础，通过演示计算理论在现代硬件和软件系统设计中的影响，把理论知识带到了现实实践之中。本书介绍了关键概念的应用，为读者在实际工作中使用计算理论提供实际指导。本书讨论的应用包括：程序设计语言、编译器、网络技术、自然语言处理、人工智能、计算生物学、安全性、博弈论、商业规则建模、标识语言、Web搜索等。本书既适合作为自动机理论课程的教程，也是相关专业人员的重要参考用书。

第1部分 简介

 第1章 为什么学习计算理论

 第2章 语言与字符串

 第3章 语言层次

 第4章 计算

第2部分 有限状态机与正则语言

 第5章 有限状态机

 第6章 正则表达式

 第7章 正则文法

 第8章 正则与非正则语言

 第9章 正则语言的算法与决策过程

 第10章 小结与参考资料

第3部分 上下文无关语言与压栈自动机

 第11章 上下文无关文法

 第12章 压栈自动机

 第13章 上下文无关与非上下文无关语言

 第14章 上下文无关语言的算法与决策过程

 第15章 上下文无关解析

 第16章 小结与参考资料

第4部分 图灵机与不可确定性

 第17章 图灵机

 第18章 church-turing命题

 第19章 停止问题的不可解决性

 第20章 可确定与半确定语言

 第21章 可确定性与不可确定性证明

 第22章 不明显提图灵机问题的语言的可确定性

 第23章 无限制文法

 第24章 chomsky层次及其他

 第25章 可计算函数

 第26章 小结与参考资料

第5部分 复杂度

 第27章 复杂度分析简介

 第28章 时间复杂度类

 第29章 空间复杂度类

 第30章 难题的实用解

 第31章 小结与参考资料

参考资料