导言与预备知识¶
导言¶
首先我们需要知道计算理论这门课应该讲的内容.一般而言,计算理论可以分为三部分内容:
- Automata Theory 自动机理论:介绍一些基本计算模型的形式化表达及它们对应的语言,即有限自动机与正则语言和下推自动机与上下文无关语言;
- Computability Theory 可计算性理论:定义图灵机,通过可计算性对问题进行分类;
- Complexity Theory 复杂度理论:通过解决一个问题的难度对问题进行分类.
本科阶段 2.0 学分的计算理论直到 2022 年都因为课时以及进度问题只涉及前两部分的内容,关于复杂度理论,我会在笔记中的计算理论进阶部分挑选几个专题做记录.
本笔记主要参考教材为《Elements of the Theory of Computation (2nd edition)》[美] Harry R. Lewis 等 著,辅助参考教材为《Introduction to the Theory of Computation (3rd edition)》[美] Michael Sipser 著。前者是本课程使用的教材,使用目的在于符号等与考试统一,后一本是经典的教程,由浅及深,通俗易懂.
预备知识¶
关于集合、关系与有限集无限集的基本定义此处不再阐述,我们从三种基本的证明方法开始.
三种基本的证明方法¶
数学归纳法
基本原理不再阐述,这是基于自然数集合的良序性定义的,接下来通过证明鸽巢原理进行应用.
鸽巢原理(抽屉原理)
定理:若
我们利用数学归纳法进行证明:
归纳奠基:若
假设
- 若存在
,使得 ,则 不是单射; - 若不存在,则考虑剩余的集合上的函数
,而此时 ,由归纳假设可知 不是单射,则存在 使得 ,根据 的定义可知也即存在 使得 ,故 不是单射,证毕.
鸽巢原理也可以推广到无限集合中,日后可以用来说明图灵机无法表达所有的语言.
对角化(Diagonalization)方法
对角化方法是一种重要的思想,我们给出一个基于关系的表述:
设
证明是简单的,我们分两种情况讨论即可:
,有 ,则必有 ; ,有 ,则必有 .
由此我们可以知道,任意
我们可以用对角化方法证明自然数的幂集
例:证明自然数的幂集
证:假设
接下来我们构造对角集为
,必有 ; ,必有 .
故不存在
闭包 Closures¶
闭包也是离散中学习过的内容,即满足一定条件(例如自反性/对称性/传递性)的包含某一关系的最小集合,例如传递闭包我们可以形式化定义如下:
传递闭包
; 是满足传递性的; 且 是传递的,则有 .
这三点综合表明传递闭包
本课程研究最多的称为自反传递闭包(考虑计算模型运行 0 步或任意步的情况),一般记为
字母表与语言 Alphabet and Language¶
我们的计算模型中实际出现的是数据编码成的字符串,因此我们正式讨论前需先了解字符串.
字母表
- 字母表是一个有穷的符号集合;
- 例如
为二进制字母表, 是经典的英文字母表; - 简单起见我们只把字母、数字和其他常用字符($、# 等)用做符号.
字符串
- 字符串是字母表中符号的有穷序列;
- 一个字符串中可以没有符号,称为空串,记为
; - 通常用
和希腊字母表示字符串,例如用 作为字符串 的名字,但是不能把一个字母既用做符号又用作名字; - 字母表
上的所有字符串(包括空串)记作 ; - 字符串的长度:# of symbols(# 一般表示 number,即个数),记作
.
字符串上的运算
连接运算 Concatenation
- 字符串
和字符串 的连接是在字符串 的后面接上 ,记作 ,或简记为 ; ;- 结合律:
; - 字符串
是 的字串(substring) ; - 如果对于某个
,有 ,则称 是 的后缀(suffix);如果对于某个 ,有 ,则称 是 的前缀(prefix).
乘方运算 Exponentiation
对于任意字符串
; .
例如
反转运算 Reversal
对于字符串
- 如果
是长度为 0 的字符串,则 ; - 如果
是长度为 的字符串,则对于某个 .
定义第二点即每次取出字符串中最后一个字母进行操作. 通俗而言字符串反转即将字符串反过来.
例:利用归纳定义证明:对于任意两个字符串
例如:
证:对
归纳奠基:
假设
其中
语言
我们研究的计算模型可以处理某一类的字符串,因此我们需要研究字符串构成的集合.
- 任意字母表
上的字符串集合(即 的任一子集)称为语言,即 . 例如 是 上的语言; - 由上述定义可知
都是语言; - 有穷语言可以列举表示,无穷语言可以通过
表示. 例如 .
显然一个有限字母表上的字符串是无限的,但其可数性是值得讨论的,我们有如下定理:
定理:如果
证:证明可数性需要构造一个双射
- 对于每一个
,所有长度为 的字符串都在所有长度为 的字符串前枚举; - 所有
个长度为 的字符串按字典序枚举(lexicographically),即如果对于某个 , 且 ,则 在 前面.
例如,对于
语言的运算
- 语言是集合,因此可以定义并、交、差、补(
)运算; - 连接运算
,可简记为 ; - 基于连接定义乘方运算
; - Kleene Star
,即连接 中 0 个或多个字符串得到的字符串集合. 还有一个概念 .
例:
例:
证:证明两个集合相等只需证明二者互相包含. 根据定义,
Remark
- 事实上记号
中的 与 Kleene Star 含义一致,将 视为单字母字符串组成的语言即可; ,原因是只能选取 0 个字符串进行连接,故结果为 ; ( 连接一个或多个 中的字符串),可以将 看作 在连接运算下的闭包,即 是包括 且在连接运算下封闭的最小语言;- 对任意的语言
有 ,注意区别于第 2 点.
语言的有穷表示¶
计算理论的一个核心问题是如何用有穷的规定表示语言. 对于有穷语言我们列举即可,但无穷语言需要更好的表示方法. 有穷表示有以下两个原则;
- 有穷表示本身是一个字符串;
- 要求不同语言有不同的表示.
但我们发现,因为有穷表示是字符串,因此只有
我们先来看一个例子:
例:令
一定注意
以上表示可以简化为
字母表
(空元,对应语言的空集)和 是正则表达式;- 若
和 是正则表达式,则 是正则表达式; - 其他表达式都不是正则表达式.
注意上述符号中括号是拆成左括号和右括号,中间逗号隔开,而不是
上述符号
请注意不要将正则表达式和语言混淆,正则表达式根据定义只是一个字符串,但我们可以通过函数
, ;- 若
和 是正则表达式,则 .
例:求
解决此类问题,重要的是首先要看出正则表达式的结构,即我们可以如何按照上面的规则进行化简,理解时可以适当拆除括号,尽量让表达式看起来不那么复杂.
例:
正则表达式有以下性质,可以理解记忆(特别是第 7、8 条,要理解其含义):
; ; ; ; ; ; ; .
Remark
- 每一个可以用正则表达式表示的语言都可以用无穷多个正则表达式表示,例如
和 总是表示相同的语言,上述性质 2-7 也可以用来等价转换; - 定义字母表
上的正则语言(regular language)类为所有可以写成 的语言 组成,其中 是 上任意正则表达式. 即正则语言是所有能用正则表达式描述的语言. 上的正则语言类恰好是语言集合 关于并、连接和 Kleene Star 的闭包(即空集或单个字母通过这些操作得到的字符串的集合); - 正则表达式无法描述所有语言,是一种不充分的规定说明方法,例如
无法被表示; - 两种语言有穷表示的类型:语言识别装置(recognition device,回答一个字符串是否属于某个语言的问题),语言生成器(generator,描述如何生成语言中的实例),二者关系也是这门课的一个重要课题.
总结:我们介绍了字母表、字符串以及语言的基本定义以及运算,表明语言是字符串的集合,并且证明了不是所有的语言都能被有穷表示. 我们介绍了一种基本但不充分的表示形式,即正则表达式,正则表达式与语言之间通过符号与集合操作的函数关系联系起来.