本书是理论计算机科学方面的优秀教材，主要介绍形式语言、自动机、可计算机和相关内容。本书特别注意定义、定理的准确性和严格性，在定理的证明中给出了直观的动机和框架，避免多余的数学细节，这有利于培养学生形式化和严格的数学推理能力，加强对问题的理解：本书通过精心设计的大量示例，生动剖析了各种定理和定义，概念清晰，深入浅出。每章后面还给出了难度不同的习题，并给出部分习题的解答，可使学生加深对基本原理的理解并增强应用能力。

本书主要介绍形式语言、自动机、可计算性和相关内容。主要内容包括：计算理论导引、有穷自动机、正则语言与正则文法、上下文无关语言及文法、下推自动机、图录机、形式语言和自动机的层次结构、计算复杂性等。每节后面都给出了习题，并包含部分习题的解答，方便教学。
本书是理论计算机科学方面的优秀教材之珂作为高等院校计算机专业的教材，也可作为计算机系统研发人员的参考书。

Peter Linz 在威斯康星大学获得博士学位，是加州大学戴维斯分校计算机科学系退休教授，其研究领域为计算机数值分析理论。除本书外，他还撰有《Exploring Numerical Methods:Fan Introduction to Scientific Computing》一书。

出版者的话
专家指导委员会
译者序
前言
第1章 计算理论导引
1.1 数学预备知识和表示
1.2 三个基本概念
1.3 一些应用
第2章 有穷自动机
2.1 确定型有穷接受器
2.2 非确这型有穷接受器
2.3 确定型有穷接受器和非确定型有
2.4 减少有穷自动机中状态的化简
第3章 正则语言与正则文法
3.1 正则表达式
3.2 正则表达和正则语言之间的联系
3.3 正则文法
第4章 正则语言的性质
4.1 正则语言的封闭性质
4.2 正则语言的基本问题
4.3 识别非正则语言
第5章 上下文无关语言
5.1 上下文无关方法
5.2 分析和二义性
5.3 上下文无关文法和程序设计语言
第6章 上下文无关文法的化简与范式
6.1 文法变换方法
6.2 两个重要的范式
6.3 上下文无关文法的成员资格
第7章 下推自动机
7.1 非确定型下推自动机
7.2 下推自动机与上下文无关语言
7.3 确定型下推自动机和确定型上下文无关语言
7.4 确定型上下文无关语言的方法
第8章 上下文无关语言的性质
8.1 两个泵引理
8.2 上下文无关语言的封闭性质和判定算法
第9章 图灵机
9.1 标准图灵机
9.2 完成复杂任务的组合图灵机
9.3 图灵论题
第10章 图灵机的其他模型
10.1 对图灵机的等价性
10.2 具有更复杂存储的图灵机
10.3 非确定型图灵机
10.4 通用图灵机
10.5 线性有界自动机
第11章 形式语言和自动机的层次结构
第12章 算法计算的限制
第13章 其他的计算模型
第14章 计算复杂性介绍
部分习题的解答和提示
参考文献
索引