计算理论是关于计算知识的有系统的整体,本是数学的一个研究领域,诞生于数理逻辑学家对计算本质的探索。这里的计算 (Computation) 并不是指纯粹的算术 (Calculation),而是指一种以 “机械而有效的” 方式获取问题答案的过程。随着计算理论的发展最终促使了计算机的发明,计算理论的重心也从数学转到了计算机科学,而计算理论关心的核心问题是:
计算(机)的基本能力和限制究竟是什么?
这个问题中包含了两个内容,分别对应计算理论的两个研究方向:可计算性理论和计算复杂性理论, 而形式语言与自动机理论正是这两个重要的研究方向的理论基础。
为了能够严谨的研究这种机械而有效的计算过程,我们需要严格定义的概念去描述它,需要严谨的计算模型去分析它。这个概念,其实就是已经被我们大家所熟知的“算法”(Algorithm);而这些模型呢,就是我们将要在课程中主要学习的自动机理论,包括有穷自动机、下推自动机和图灵机等几种自动机装置,还包括一些与自动机形式上不相似但能力上却完全相同的模型,如正则表达式和文法等。
形式语言与自动机理论是计算机科学与技术领域基本的思想和方法,它不仅是编译技术的基础,在诸如计算机网络协议、文件搜索、数字电路设计和验证等诸多领域也发挥着重要作用。本课程旨在培养学生形式化描述和抽象思维能力,掌握“问题——形式化描述——自动化(计算机求解)”的思想和方法,并用于解决实际问题。
课程目标1:掌握正则语言与上下文无关语言等语言的形式化描述方法和识别方法,能够设计与之相应的文法和自动机,培养学生的抽象思维能力和逻辑思维能力。
课程目标2:分类研究语言的性质,培养针对不同语言的模型描述能力和模型计算能力(包括模型的等价变换、推理等),能够在更高的抽象层面处理复杂工程问题,进而尝试探讨问题的可计算性及其计算的复杂性。
课程目标3:掌握由问题到形式化描述、再到计算机化的问题求解方法,能够对实际问题进行抽象、形式化,构建计算模型,进而用计算机予以解决。
第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章 测试 图灵机与不可判定性
集合论与图论