本书共分形式语言与自动机理论，可计算理论，逻辑学，程序设计理论等四个部分。内容包括：语言与正规语言；有限自动机；短语结构语言与上下文有关语言；可计算理论；模糊逻辑等。本书内容丰富，讲解通俗易懂，具有很强的可读性。

第一部分 形式语言与自动机理论

第一章 语言与正规语言

 1.1 符号、符号串及其运算

 1.2 文法与语言的形式定义

 1.3 正规表达式

 1.4 正规文法与正规式

第二章 有限自动机

 2.1 有限自动机的定义与构造

 2.2 确定的有限自动机(DFA)

 2.3 不确定的有限自动机(NFA)

 2.4 NFA的确定化

 2.5 DFA的最小化

 2.6 正规集与有限自动机的等价性

 2.7 双向有限自动机

 2.8 具有输出的有限自动机

第三章 正规集的性质

 3.1 正规集的泵作用引理

 3.2 正规集的封闭性质

 3.3 正规集的一些判定算法

第四章 上下文无关语言

 4.1 上下文无关文法

 4.2 上下文无关文法的简化

 4.3 Chomsky范式

 4.4 Greibach范式

 4.5 先天歧义的上下文无关语言的存在

第五章 下推自动机

 5.1 非形式的描述

 5.2 下推自动机的定义

 5.3 下推自动机和上下文无关语言

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

 6.1 对CFL的泵作用引理

 6.2 上下文无关语言的封闭性质

 6.3 CFL的某些判定算法

第二部分 可计算理论

第七章 图灵机

 7.1 图灵机模型

 7.2 可计算语言和函数

 7.3 图灵机的构造技术

 7.4 图灵机的修改

 7.5 Church假设

 7.6 图灵机作为枚举器

 7.7 等价于基本模型的受限图灵机

第八章 短语结构语言与上下文有关语言

 8.1 短语结构语言与图灵机

 8.2 上下文有关语言与线性有界自动机

 8.3 上下文无关语言与递归集合

 8.4 上下文有关语言类的性质

第九章 可判定性

 9.1 递归语言和递归可枚举语言的性质

 9.2 通用图灵机和一个不可判定问题

 9.3 RICE定理和某些其他的不可判定问题

 9.4 POST对应问题的不可判定性

 9.5 图灵机的有效计算和无效计算

 9.6 Greibach定理

 9.7 圣人计算

第十章 可计算理论

 10.1 原始递归函数

 10.2 递归函数与部分递归函数

 10.3 图灵机与部分递归函数的等价性

第三部分 逻辑学

第十一章 命题逻辑与一阶逻辑

 11.1 命题逻辑的自然推理

 11.2 命题演算的公理系统

 11.3 PC的可靠性与一致性

 11.4 PC的完备性

 11.5 一阶逻辑

第十二章 直觉主义逻辑

 12.1 直觉主义的一些基本观点

 12.2 一阶直觉主义逻辑的形式化

 12.3 完全性定理

第十三章 模态逻辑

 13.1 模态词“必然”与“可能”

 13.2 模态命题逻辑系统

 13.3 模态狭义谓词逻辑

第十四章 非单调逻辑

 14.1 单调性与非单调性

 14.2 非单调逻辑

 14.3 缺省推理

 14.4 非单调逻辑系统

 14.5 限定理论

第十五章 模糊逻辑

 15.1 逻辑与不确定性的研究

 15.2 模糊集

 15.3 模糊逻辑的代数模型——De-Morgan代数

 15.4 模糊变量与模糊逻辑公式(函数)

 15.5 模糊逻辑真值表与范式

 15.6 模糊逻辑公式的极小化

 15.7 似然推理

 15.8 模糊归纳推理

第十六章 多值逻辑

 16.1 三值逻辑

 16.2 多值命题逻辑

 16.3 三值逻辑代数系统

 16.4 n值逻辑代数系统

 16.5 阈值逻辑

第四部分 程序设计理论

第十七章 程序的指称语义

 17.1 把程序看作函数

 17.2 序列程序结构的程序函数

 17.3 分支程序结构的程序函数

 17.4 循环程序结构的程序函数

 17.5 循环程序的正确性证明

第十八章 程序的公理语义

 18.1 程序的公理语义

 18.2 霍尔公理系统

 18.3 最弱前置谓词与程序的公理语义

第十九章 程序的形式推导

 19.1 程序形式推导的基本思想

 19.2 选择语句的设计

 19.3 循环程序的设计

 19.4 不变式与界函数的构造

第二十章 递归程序理论

 20.1 递归的基本概念

 20.2 递归数据结构

 20.3 递归程序的证明

习题

参考文献