串和语言
记字母表为 ,
若干字母组合成为字符串 , 记 为所有字符串的集合, 为空串, 语言 为字符串的集合, 为空语言, 且 .
设 是两个语言,
可以定义正则运算:
有穷自动机
有穷自动机是一个五元组 , 其中:
- 是状态集合
- 是字母表集合
-
是状态转移函数
- 是起始状态
- 是接受状态集
特别地,
可以做一些额外的扩展定义, 这在证明正则语言对正则运算封闭是相当有用的,
比如
可以接受一个串而不是一个字母.
有穷自动机的计算
给定
以及输入的字符串 ,
的计算是一个状态序列 满足:
若 , 则称 接受 , 将 接受的所有语言记作 .
由有穷自动机所识别的语言称为正则语言.
定理1 正则语言类对正则运算封闭.
证明方法是构造新的自动机使得它能识别并,
连结和星号运算得到的语言.
非确定性有穷自动机
简称 NFA. 一个 NFA
仍然是五元组 , 其中:
- ,
也可以记作 .
- , 这表明每一次转移产生一个状态集, 这个状态集可以是空集.
- 其余定义和 DFA 保持一致.
DFA 的计算是一个状态序列, 而 NFA 的计算是多个状态序列,
这些状态序列是一颗状态树从根节点到所有叶子节点的路径上的状态形成的序列.
根节点为起始状态 ,
只要有叶子结点对应的状态为接收状态, 就表明 NFA 接受一个语言, NFA
每读入一个字符就会产生若干个自动机的副本,
可以认为这些自动机的计算是并行的.
NFA 和 DFA 的等价性
定理 2 NFA 和 DFA 识别同样的语言.
听起来让人感到惊讶, 因为 NFA 是 DFA 的推广, 直觉上, NFA
应该能识别更多种类的语言.
证明方法就是构造一个 DFA 使得它能模拟一个给定的 NFA.
Proof 对于 , 先不考虑 , 构造 ,
满足
- , 其中 . 这就是对于每一个 的状态, 得到的新状态也是 的子集, 这里面的每一个状态都通过 中的状态转移得来.
- , 就是所有包含 中的元素的那些集合.
如果要考虑 , 则先引入
-闭包 为 中的状态仅沿着 可以到达的状态集, 同时也包括
自身, 那么做修改
即可.
用 NFA 可以更容易地证明正则语言对正则运算的封闭性:
- 并: 设 分别识别 , 增加初始状态 仅以 分别指向 的初始状态 即可.
- 连结: 的所有接收状态都以
指向 的初始状态.
- 星号: 增加一个新的初始状态用于识别空串, 然后所有的接收状态都以 指向旧的初始状态.
正则表达式
单个字母, 空串, 空语言和正则表达式的并, 连结和星号定义为正则表达式.
这说明正则表达式是归纳定义的.
再定义 ,
.
定理 3 正则表达式与 DFA 是等价的,
它们能描述同一种语言.
正则表达式描述正则语言, 正则语言可以被正则表达式描述.
定理 4 (泵引理) 若 是一个正则语言, 则存在 使得对于任一 , 都可以被分成三段 , 满足
图灵机
图灵机(Turing Machine, TM)中最简单的模型为单带 TM, 单带 TM 是一个七元组 ,
拥有一条(单向)无限长的 tape 以及读写头, 其中:
- 是工作字母表, 设 为空格, 一般有 ,
表示图灵机能写在带子上的字符集.
- 为状态转移函数,
表示图灵机接受当前读写头所指的字母转移到一个新的状态并将该字母修改为
中的一个字母(可以不变),
表示读写头移动的方向.
-
分别为接受状态和拒绝状态.
其余定义和自动机保持一致.
可以看出单带图灵机的特点是双向读写头,
图灵机的状态包括三种:
图灵机的格局指的是图灵机的:
比如格局 表示:
- 当前状态为
- 当前扫描内容为
- 当前带子的内容为 , 其中
为 左边的内容, 为 右边的内容.
图灵机的初始格局为 , 其中
为输入到图灵机中的字符串.
一个格局可以产生另外一个格局, 设 ,
若转移函数 满足 , 那么格局 产生的格局为 .
当假定带子是单向有界且当前读写头扫描内容为左/右边界处的字符时,
则转移函数要求向左/右移动时只修改不移动.
单带 TM 在串
上的计算是格局的序列, 当序列有穷时图灵停机,
最后一个格局对应的状态决定是接受还是拒绝; 当序列无穷时不停机.
Church-Turing thesis
算法是处处停机的图灵机.
时间复杂性
令
是一个在所有输入上都停机的确定性图灵机, 的运行时间或者时间复杂度是一个函数
且 表示 在所有长度为 的输入上运行所经过的最大步数.
定义时间复杂性类 为由
时间的图灵机判定的所有语言的集合. 比如可以验证 ,
这可以转化成一个算法的设计
(根据图灵机读写头的特点类比指针设计一个复杂度为 的算法来判断一个字符串是否是形如
的,
根据此算法可以构造一个单带确定型图灵机 ).
当然实际上可以设计出一个更好的单带图灵机 使得 ,
如果是多带图灵机, 则可以在
时间内判定 ,
这些例子说明了语言的复杂度和选择的计算模型有关.
那么自然就要考虑不同模型之间的复杂性关系,
也就是计算模型的选择到底是怎么影响语言的时间复杂度的.
可以证明每一个
时间的多带图灵机都和一个
时间的单带图灵机等价,
只需要对于给定的多带图灵机用一个单带图灵机来模拟它即可.
那非确定型 TM 呢? 可以证明每一个 时间的非确定型单带 TM 都和某一个
时间的确定型单带 TM
等价, 证明方式同样是用确定型单带 TM 来模拟非确定型单带 TM.
类
集合
是确定型单带图灵机在多项式时间内可判定的语言类, 也就是说
大致对应于在计算机上实际可解的那些问题.
对于所有与确定型单带 TM 等价的计算模型而言, 是不变的, 这意味着 在数学上具有稳健性.
类
定义语言
的验证机 (verifier) 是一个算法 , 即 .
被称为
的成员资格证书或者一个证明. 比如对于问题 构造验证机
1
2
3
4
5
| V="对输入<<G,k>,c>:
1) 检查 c 是否是 G 中 k 个结点的集合;
2) 检查 G 的边集是否包含连接 c 中结点的所有边(即判断 c 是否是个团);
3) 若两项检查都通过, 则接受, 否则拒绝.
"
|
将一个语言的证书交给该语言的 verifier 后,
如果能在多项式时间内检查输入是否在语言中, 就称该语言具有多项式时间的
verifier, 定义
是具有多项式时间验证机的语言类. 可以证明一个语言在
中当且仅当它能被某个非确定型多项式时间图灵机判定.
这个类的名称
就来源于非确定型多项式时间 TM.
对于某些
问题的补问题, 定义它们属于 , 包括 中问题的补问题, 不清楚 与 是否相等.
-complete
规约
对于函数 ,
若存在多项式时间图灵机
使得在任何输入 上, 停机时 恰好在 的带子上, 则称
为多项式时间可计算函数.
若存在多项式可计算函数
使得对于语言 以及每一个, 都有 , 则称语言
多项式时间映射可规约(简称多项式时间可规约)到语言 , 记作 , 称为 到 的多项式时间规约.
直觉上若 , 则 , 这是正确的, 只需要根据
的多项式时间算法 与多项式时间可计算函数 构造出 的一个多项式时间算法 即可: 对于 , 先在多项式时间计算出 , 然后将 输入到 中, 这一定会被 接受,
那么将这两个过程作为一个整体就构造出了一个在多项式时间内判定 的一个图灵机, 这就意味着 .
现在给出一个非常经典的多项式规约: 由 归约到 .
定义 , , , 现在需要构造出多项式时间可计算函数 使得 .
构造 , 除了满足每个三元组 内部无边外,
对于不同三元组中的点 , 若 则 , 反之不相连, 这个 可以在 内用 构造出 , 只需要枚举每一对文字即可. 现在证明
可满足当且仅当 有 -clique.
当 可满足时,
每个子句至少含有一个值为 的文字,
在 中选择这些点,
这些点不在同一个三元组而且也不可能是相反的两个文字,
那么这些点就一定互相相连, 这就是
的一个 -clique.
当 有 -clique 时, 每个三元组恰好有个点在 中, 将 每个点在 中对应的文字赋值为 , 就可以使 得到满足.
这就结束了证明.
-complete
-complete 简称 .
Stephen Cook 和 Leonid Levin 发现若
中的某些问题存在多项式时间算法, 那么
中的所有问题都是多项式时间可解的, 定义这些问题是 -complete, 对应的集合写成
. 这样一来为了证明探究
是否成立,
只需要关注
中的一个问题即可.(当然好像 更可能成立, 因此当一个问题属于 时,
似乎就给该问题的难解性提供了一个有力证据.)
更规范的定义是, 如果语言
满足下面两个条件:
- , .
则称 是 -complete (完全的, 也可以写成 ).
可以看作是 上的序关系,
而且它至少具有传递性和自反性.
-Hard
相较于 -complete,
-Hard
的问题只需满足上面的条件 2, 也就是说, 如果语言 满足 , , 但是不知道 与 的关系, 那就称语言 是 -Hard 或者 难的.
Levin-Cook 定理
证明
是简单的, 主要困难在于如何证明 中的每个问题都可多项式归约到
, 这等价于证明 是 的.
