计算理论基础

第1章 数学基础

1.1 引言

1.2 集合

1.3 关系与图

1.4 函数与计数

1.5 证明技巧

1.6 本章总结与习题

本章习题

第2章 正则语言

2.1 引言

2.2 语言基础

本节习题

2.3 正则表达式

本节习题

2.4 正则语法

本节习题

2.5 确定性有限自动机（DFA）

本节习题

2.6 非确定性有限自动机（NFA）

本节习题

2.7 本章总结与附加思考题

附加思考题

第3章 等价

3.1 引言

3.2 NFA到DFA

本节习题

3.3 有限自动机与正则语法

本节习题

3.4 正则表达式到NFA

本节习题

3.5 NFA到正则表达式

本节习题

3.6 本章总结与附加思考题

附加思考题

第4章 正则语言的结构

4.1 引言

4.2 闭包性质

本节习题

4.3 非正则语言

本节习题

4.4 米歇尔-尼罗德定理

本节习题

4.5 状态最小化

本节习题

4.6 本章总结与附加思考题

附加思考题

第5章 上下文无关语言

5.1 引言

5.2 上下文无关语法

本节习题

5.3 分析树

本节习题

5.4 歧义

本节习题

5.5 消除／删除不良生成式

本节习题

5.6 范式

本节习题

5.7 本章总结与附加思考题

附加思考题

第6章 上下文无关语言的结构

6.1 引言

6.2 叠加自动机

本节习题

6.3 上下文无关语法与叠加自动机

本节习题

6.4 泵作用引理

本节习题

6.5 上下文无关语言的闭包性质

本节习题

6.6 确定型叠加自动机

本节习题

6.7 本章总结与附加思考题

附加思考题

第7章 可计算枚举语言

第8章 非可计算枚举语言

第9章 算法可解性

第10章 计算复杂性

部分习题答案与提示

参考文献

《世界著名计算机教材精选：计算理论基础》讨论了计算机科学中的纯粹、引人注目并且普遍存在的基本内容，介绍构成基本计算范例的基本概念、模型、技巧、结果，阐述当今计算机科学家用于建模、讨论和预测算法与计算的思想概念与数学知识。全书共分10章，内容包括数学基础、正则语言、上下文无关语言、可计算枚举语言、非可计算枚举语言、算法可解性、计算复杂性等内容。每章都给出了大量习题，并且在附录提供了部分习题的答案与提示。 　　《世界著名计算机教材精选：计算理论基础》可以作为计算机科学、计算机工程和数学等专业的本科核心课程教材，适用于计算理论、自动化理论、形式语言和计算模型等方面的课程。