计算理论是关于计算知识的有系统的整体，本是数学的一个研究领域，诞生于数理逻辑学家对计算本质的探索。这里的计算 (Computation) 并不是指纯粹的算术 (Calculation)，而是指一种以 “机械而有效的” 方式获取问题答案的过程。随着计算理论的发展最终促使了计算机的发明，计算理论的重心也从数学转到了计算机科学，而计算理论关心的核心问题是：
计算（机）的基本能力和限制究竟是什么?
这个问题中包含了两个内容，分别对应计算理论的两个研究方向：可计算性理论和计算复杂性理论, 而形式语言与自动机理论正是这两个重要的研究方向的理论基础。
为了能够严谨的研究这种机械而有效的计算过程，我们需要严格定义的概念去描述它，需要严谨的计算模型去分析它。这个概念，其实就是已经被我们大家所熟知的“算法”(Algorithm)；而这些模型呢，就是我们将要在课程中主要学习的自动机理论，包括有穷自动机、下推自动机和图灵机等几种自动机装置，还包括一些与自动机形式上不相似但能力上却完全相同的模型，如正则表达式和文法等。
第1章 课程简介和基础知识
1.1 课程简介
1.2 基础知识
第1章 测试 基础知识
第2章 有穷自动机
2.1 确定的有穷自动机
2.2 非确定有穷自动机
2.3 带有空转移的非确定有穷自动机
第2章 测试 有穷自动机
第3章 正则表达式
3.1 正则表达式
3.2 自动机和正则表达式
3.3 正则表达式的代数定律
第3章 测试 正则表达式
第4章 正则语言的性质
4.1 正则语言的泵引理
4.2 正则语言的封闭性
4.3 - 4.4 正则语言的判定性质&自动机最小化
作业1
第4章 测试 正则语言的性质
第5章 上下文无关文法
5.1 上下文无关文法
5.2 - 5.3 语法分析树&文法和语言的歧义性
5.4 文法的化简和范式
第5章 上下文无关语言
第6章 下推自动机
6.1 下推自动机
6.2 下推自动机的语言
6.3 下推自动机与文法的等价性
6.4 确定型下推自动机
第6章 测试 下推自动机
第7章 上下文无关语言的性质
7.1 上下文无关语言的泵引理
7.2 上下文无关语言的封闭性
7.3 上下文无关语言的判定性质
第7章 测试 上下文无关语言的性质
第8章 图灵机与不可判定性
8.1 图灵机
8.2 不可判定性
第8章 测试 图灵机与不可判定性