计算理论笔记

本文记录了 0xfaner 对计算理论的理解。

写在前面

本文将介绍计算理论中的一些基本概念以及一个最简单的计算模型:自动机模型。

自动机模型能解决的问题相当有限,但它是图灵机模型的基础,并且足够简单。选择从自动机模型入门计算理论再合适不过。

有学习过《算法导论》中的字符串匹配部分的同学应该对自动机理论并不陌生。介于自动机模型和图灵机模型之间的,有一个下推自动机模型,其功能强于自动机但弱于图灵机,是程序语言理论中研究的核心模型。不过 0xfaner 暂时无意接触程序语言理论,因此本文也不介绍下推自动机.

计算问题

什么是计算机?

计算,就是解决某个具体问题的 算法 ,得出相应的答案。

计算机就是能执行某个具体算法的机器。即 Computer 就用来是 Compute 的机器。这里无需对“机器”的定义刨根问底,因为对我们研究计算机科学毫无帮助,我们只需要知道,计算机是用来执行算法的机器。我们要做的是,用最简单的理论模型,最大程度的抽象化我们现有的计算机.

字母表

字母表 是符号的有穷非空集合, 通常使用 $ \Sigma $ 表示。

例如:

  1. $ \Sigma = \{0, 1\} $ , 二进制字母表。
  2. $ Σ = \{a, b, \dots, z\} $ , 所有小写字母集合。

是从某个字母表中选择符号的有穷序列。

例如: $ 010101 $ 是从 $ \Sigma = \{0, 1\} $ 中选出的串。

  • 空串:是出现 $ 0 $ 次符号的串,记作 $ ε $ 。它是可以从任何字母表中选择的串。
  • 串的长度:标准记号为 $ |w| $ , $ |ε|=0 $ 。
  • 字母表的幂:定义 $ \Sigma^k $ 为长度为 $ k $ 的串的集合,串的每个符号都属于 $ Σ $ 。字母表的所有串的集合约定记为 $ \Sigma^\ast $ 。

语言

$ \Sigma $ 是某个具体的字母表,全都从 $ \Sigma^\ast $ 中选出的串的一个集合称为 语言 。如果 $ \Sigma $ 是字母表,且 $ L \subseteq \Sigma^\ast $ ,则 $ L $ 是 $ \Sigma $ 上的语言。

例如字母表 $ \Sigma=\{0, 1\} $ ,则我们可以定义一个 $ \Sigma $ 上的语言:

则该语言为

我们也可用形式化的描述来定义语言:

设 $ \Sigma $ 是一个字母表, $ \Sigma^0=\{\varepsilon\} $ 表示空串的集合。

$ \Sigma^n=\Sigma\times \Sigma\times\cdots\times \Sigma $ 为 $ n $ 个 $ \Sigma $ 的直积。

则 $ \Sigma $ 上的一个语言定义为 $ \Sigma^\ast=\bigcup\limits_{i\in\mathbb{N}}\Sigma^i $ 的子集.

语言有着极其强大的应用,这里举一个有意义的例子:

一个语言可以用来表示所有的有向无环图(英文名 Directed acyclic graph,简称 DAG)。

我们试图用字母表 $ \Sigma=\{0,1\} $ 上的语言来对图进行编码。首先我们需要表示图 $ G=(V,E) $ 中的 $ V $ 。

我们约定 $ \dagger $ 之前的部分表示图中每个点的名称的长度 $ v $ ,而 $ \dagger $ 之后依次的每个长度为 $ v $ 的连续子串表示图所有点的名称。在所有的名称后, 我们用另一个 $ \dagger $ 作为分割,其后依次的每个长度为 $ 2v $ 子串表示一条有向边。所有的有向边后以 $ \ddagger $ 结束。例如下图:

可以被表示为

在上述编码中,作如下替换

即为该有向无环图在该语言中的编码。所有的有向无环图构成的语言,即所有的有向无环图按照上述编码构成的语言。值得一提的是。上述语言对有向图的编码并不是双射,但是我们可以添加适当的限制使得该语言对有向图的编码成为双射。

按照类似的方式,我们可以用语言表示所有的合取范式、无环布尔电路、树等。大多数情况下,我们不讨论具体的编码方式,而是直接讨论语言,如“所有的合取范式构成的语言”。

问题

问题 就是判定给定的串是否属于某个具体语言的提问。

如果 $ \Sigma $ 是字母表, $ L $ 是 $ \Sigma $ 上的语言,则问题 $ L $ 就是:给定 $ \Sigma^* $ 中的一个串 $ w $ ,判定 $ w $ 是否属于 $ L $ 。

有些问题只能用“是”与“否”回答,例如问某个有向图是不是有向无环图,因此也被称为判定问题。

判定问题的算法实际上是建立了一个映射。如果用 $ L_{G} $ 表示所有的有向图构成的语言,并用 $ 0,1 $ 分别表示“是”与“否”,那么这个判定问题实际上就是建立了一个映射 $ f:\{0,1\}^\ast\to \{0,1\} $ ,且 $ f(x)=1 $ 当且仅当 $ x\in L_G $ 。而解决这个判定问题的算法就是能够计算函数 $ f $ 的算法.

不难得出,每一个语言都对应一个判定问题,因此我们不再区分语言和判定问题,我们可以直接说判定问题 $ L_G $ 。即判定一个有向图是否为有向无环图的问题。

为什么我们要如此关注判定问题?因为在未接触到这方面理论的人的直观思维中,判定问题是一类非常弱的问题,弱到连自然数的加法都无法计算。确实如此,但是判定问题和非判定问题之间存在天然的关系,每一个非判定问题都可以转换为判定问题。

例如,给定计算问题:

可以转换为判定问题:

其中 $ g(x,y,z)=1 $ 当且仅当 $ x+y=z $ ,即判定 $ z $ 是否为 $ x $ 和 $ y $ 的和的问题。而且两者的复杂度之间存在深刻的关系。

自动机模型

有限状态机

有限状态自动机,英文名 finite state machine,简称 FSM 。

一个 FSM 可以被描述为一个五元组 $ (Q,\Sigma,\delta,q_0,F) $ ,其中:

  1. $ Q $ 是一个有限集,称为状态集
  2. $ \Sigma $ 是一个有限集,称为字母表
  3. $ \delta:Q\times\Sigma \to Q $ 称为转移函数
  4. $ q_0\in Q $ 是起始状态
  5. $ F\subseteq Q $ 是接受状态集

有限状态机也称为自动机,英文名 automaton。

一个自动机可以用一张类似于这样的图表示:

  • 圆圈表示状态
    • 有一条没有起点的箭头指向的状态为起始状态
    • 双圈表示的状态是接受状态
  • 带符号集的箭头表示转移函数中的一组映射
    例如 $ q_2\overset{0,1}{\longrightarrow}q_3 $ 表示映射 $ (q_2,0)\mapsto q_3 $ 和 $ (q_2,1)\mapsto q_3 $ 两条映射

当自动机处于某个状态的时候,读取到相应的符号,自动机会根据转移函数跳转到下一状态。例如上图中,当自动机处于 $ q_1 $ 状态时,如果读到的下一符号为 $ 0 $ ,根据转移函数 $ (q_1,0)\mapsto q_1 $ ,则在读取该符号后,自动机仍会处于 $ q_1 $ 状态。

注意

有限状态机(finite state machine)也可以称为自动机(automaton),但不能称为”有限自动机”。

我们说”自动机”就是指”有限状态机”,而不是”有限状态机””下推自动机””非确定自动机”等一系列计算模型的统称。

复杂度类REG

现在我们要讨论一类相当简单的语言,和由它们构成的复杂度类 REG.

依据之前有关于自动机的描述,我们知道当自动机 $ M=(Q,\Sigma,\delta,q_0,F) $ 处于起始状态 $ q_0 $ 时,我们输入一个 $ \Sigma $ 上的串 $ x\in\Sigma^\ast $ ,$ M $ 会依次读取串 $ x $ 上的符号,并根据状态机作相应的状态转换。

当整个串 $ x $ 读取完毕后,$ M $ 可能处于某个接受状态 $ q\in F $ ,也可能处于某个非接受状态 $ q^\prime\notin F $ 。如果一个串 $ x\in \Sigma^\ast $ 使 $ M $ 按照上述运行方式运行后,处于某个接受状态,那么称 $ M $ 接受串 $ x $ ,记作 $ M(x)=1 $ ,否则称 $ M $ 拒绝串 $ x $ ,记作 $ M(x)=0 $ 。

注意拒绝状态有两种情况. 一种是在输入结束后自动机确实处于某个非接受状态. 另一种是在输入的过程中某一步转移失败了,即转移函数中并没有对应的映射,此时计算将提前中止。

根据这种运行方式,自动机 $ M $ 可以表示一个映射 $ f: \Sigma^\ast\to\{0,1\} $ 满足 $ f(x)=1 $ 当且仅当 $ M(x)=1 $ 。如果一个语言 $ L $ 和一个自动机 $ M $ 满足 $ x\in L $ 当且仅当 $ M(x)=1 $ ,我们就说 $ M $ 识别 (recognize) $ L $ 或者 $ M $ 判定 (decide) $ L $ 。

为了统一我们有关判定问题的叙述,本文统一使用”判定”.

再次强调,自动机是按照输入和转移函数按部就班地执行的。输入串中每一个符号都会让自动机执行且只执行一步,因此自动机总是在输入结束的时候停机,因此不会出现不停机的情况。在这样的限制下识别和判定是等价的,但是对于其他的计算模型来说,这两个概念并不等价。

现在我们定义一类判定问题(一个语言对应一个判定问题,判定问题的集合就是语言的集合):

REG 表示那些能够被一台自动机识别的语言。

例如: $ L $ 表示所有包含字符串 $ 001 $ 的字符串的集合,若$ L\in \textsf{REG} $ ,那么一个能够识别它的自动机如下图:

自动机作为计算机

自动机可以被视为一台计算机,不过是一台功能相当弱的计算机。因为自动机没有任何类似于内存的结构,所有必须依靠存储中间值才能完成的判定问题都不能被自动机完成。我们称一个计算模型能够解决问题的能力为计算能力,如果考虑的是判定问题,那么它表示的就该模型能够判定的语言的集合的一些特征(如和其他模型能够判定的语言的)。

正则语言与自动机

正则语言

现在我们语言的三种运算方式,它们的运算结果仍是一个语言. 设 $ L_1 $ 与 $ L_2 $ 均为语言,定义它们之间的三种运算:

即 $ L_1\circ L_2 $ 是所有 $ L_1 $ 中的串与 $ L_2 $ 中的串拼接构成的串的集合,在不产生歧义的情况下,该符号可以省略。根据 concatenation 的翻译,我们可以称该运算为”串联”。

它所表示的意义类似于集合的并.

而 $ L_1^\ast $ 表示的是由 $ L_1 $ 中的任意串重复任意次(重复 $ 0 $ 次将得到 $ \varepsilon $ )所得到的所有的串构成的集合。

例如 $ L_1=\{00, 01\} $ ,那么 $ \varepsilon,00,01,0000,0101,000000,010101 $ 等都是 $ L_1^\ast $ 的元素.

从形式化定义的角度, $ L_1^\ast $ 可以定义为:

这三种运算称为正则运算,这里无需过度纠结运算的优先级问题,我们只要在需要的时候用括号强行规定运算顺序就可。

从正则运算出发,我们可以定义正则语言,英文名 regular language。它包括一类最基本的语言以及这类最基本的语言按照上述三种运算产生的语言.

一个语言 $ L $ 是正则语言, 如果它满足以下命题之一:

  1. $ L=\{a\} $ ,其中 $ a $ 是某个字母表 $ \Sigma $ 上的符号
  2. $ L=\{\varepsilon\} $
  3. $ L=\emptyset $
  4. $ L=L_1\cup L_2 $ ,其中 $ L_1 $ 和 $ L_2 $ 均为正则语言
  5. $ L=L_1\circ L_2 $ ,其中 $ L_1 $ 和 $ L_2 $ 均为正则语言
  6. $ L=L_1^\ast $ ,其中 $ L_1 $ 为正则语言

上述4.5.6.的运算中空集也可以参与,并且有:

  1. 空集与任何语言做 $ \circ $ 或 $ \cup $ 运算得到的都是空集
  2. $ \emptyset^\ast=\{\varepsilon\} $

这两点实际上也可以通过这些运算的定义得出。

初次接触正则语言可能会觉得有些奇怪,但是我们在学习正则表达式与了解自动机与正则语言的关系后,这个概念会变得更加清晰.

从正则语言的定义种可以得到,一个仅包含有限个串的语言总是一个正则语言,因为它可以写成它的所有单个串构成的语言的 $ \cup $ ,而每个单个串构成的语言又可以看作是仅有一个长度为 $ 1 $ 的串构成的语言的并联。

正则表达式

注意! 我们这里介绍的并不是用于在Linux系统中查询的正则表达式, 尽管我们介绍的正则表达式和它的功能一致. 但我们也会对Linux系统中的正则表达式某些符号的具体意思做出解释.

正则表达式,英文名 regular expression 。正则表达式是用来描述正则语言的,它由字母表种的符号, $ \cup $ 运算符, $ \circ $ 运算符, $ ^\ast $ 运算符以及括号组成。我们可以用这些符号连同括号的组合来表示一个正则语言,同样这里的 $ \circ $ 运算在不产生歧义的情况下可以略去。

例如正则表达式 $ R = (0\circ(0\cup 1))^\ast $ , 表示语言:

这表示所有长度为偶数且 $ 1 $ 只出现在从左至右第偶数位的串。

它的原理很简单, 它由长度为 $ 2 $ 的单元 $ 0\circ (0\cup 1) $ 重复任意次组成。而在一个单元中,第一位必须是 $ 0 $ ,第二位可以是 $ 1 $ 或 $ 0 $ 。

这个语言也是正则语言,令 $ L_0=\{0\}, L_1=\{1\} $ ,那么有:

显然符合正则语言的定义:

一个表达式 $ R $ 为正则表达式, 如果它是以下几种表达式之一:

  1. $ a $ , 其中 $ a $ 是字母表 $ \Sigma $ 中的一个元素
  2. $ \varepsilon $
  3. $ \emptyset $
  4. $ (R_1\cup R_2) $ ,其中 $ R_1 $ 和 $ R_2 $ 是正则表达式
  5. $ (R_1\circ R_2) $ ,其中 $ R_1 $ 和 $ R_2 $ 是正则表达式
  6. $ (R_1^\ast) $ ,其中 $ R_1 $ 是正则表达式

这里也要注意和空集的运算,与正则语言类似,这里不再赘述。

可以看出正则语言和正则表达式非常相似。注意有时候我们会简化正则表达式的写法,让整个串充当一个字母的角色, 并且可以用或( $ | $ )连接一些串, 同时出现可选串( $ [] $ ),例如:

表示语言:

这里每个串都是一些仅有字母表中一个符号构成的语言的串联。或( $ | $ )表示的就是 $ \cup $ , $ [x] $ 表示的是 $ x|\varepsilon $ 。以这种方式表达的正则表达式就是我们常用于查询的正则表达式。

而如果或( $ | $ )连接的是一些长度为 $ 1 $ 的串,我们也将它表示为这些串的符号的集合,例如 $ (a|b|c)^\ast $ 可以表示为 $ \{a,b,c\}^\ast $ , 如果这个集合就是字母表 $ \Sigma $ , 我们还可以写作 $ \Sigma^\ast $ 。

如果我们希望重复一个串 $ x $ 多次也可以用 $ x^+ $ 来表示, 即 $ x^+=x \circ (x^\ast) $ 。

例子

设 $ \Sigma=\{0,1\} $

  1. $ 0^\ast 10^\ast=\{w|w恰好有一个1\} $
  2. $ (\Sigma\Sigma\Sigma)^\ast=\{w|w的长度正好是3的倍数\} $
  3. $ 2333(3^\ast)=\{w|w是由2333开头且在之后是任意长度的纯3串\} $

上述3.中表示的正则表达式有助于屏蔽弹幕中那些过长的类 $ 233 $ 串, 例如 $ 2333333333333333333333 $ 。

注意,我们始终没有证明正则语言和正则表达式的对等性,即一个正则表达式表示一个正则语言,一个正则语言总可以用一个正则表达式表示。由于作者的精力限制,本文不打算证明这一点,如果有需要,可以阅读相关教材或论文来加以拓展。

定理1

一个语言 $ L $ 是正则语言,当且仅当它能够被表示成某个正则表达式 $ R $ 。

非确定自动机

非确定性

非确定性(英文名 nondeterminism)不是非确定自动机独有的,我们还会在其他的计算模型中遇到非确定性。

在自动机模型中,一个自动机在接受相同的输入时,总是执行相同的计算步骤,并总是得到相同的结果,这样的计算方式称为确定的(英文名 deterministic),其计算步骤与时间无关。

而非确定性就与确定性相反,一台具有非确定性的计算机, 在接受相同输入时,计算步骤和结果可能有所不同。

非确定自动机

自动机具有确定性是因为无论自动机处在任意状态,其对于某个具体的输入,根据转移函数,其转移的结果是唯一的,要么转移到那个唯一的结果,要么转移失败,计算终止。如果我们对这个规则进行修改,将转移的方式改为不确定的,那么我们就得到非确定自动机(英文名 nondeterministic automaton)。

现在我们回顾一下一个概念: 超集。有限集的超集非常容易理解:一个有限集 $ S $ 的超集是它的所有子集的集合,记作 $ \mathcal{P}(S) $ 。例如 $ S=\{a,b,c\} $ ,那么它一共有 $ 8 $ 个子集:

其超集就是以上 $ 8 $ 个集合组成的集族(一般我们称集合的集合为集族,也可简称为族)。

这样我们就可以给出非确定自动机的定义:

一个非确定自动机是一个五元组 $ (Q,\Sigma_{\varepsilon},\delta,q_0,F) $ ,其中:

  1. $ Q $ 是一个有限集, 称为状态集
  2. $ \Sigma_{\varepsilon} $ 是一个有限集,是字母表和空串 $ \varepsilon $ 的并集
  3. $ \delta:Q\times\Sigma_\varepsilon \to \mathcal{P}(Q) $ ,称为转移函数
  4. $ q_0\in Q $ ,是起始状态
  5. $ F\subseteq Q $ ,是接受状态集

非确定自动机与自动机相比,唯一的不同在于转移函数,非确定自动机的转移函数的上域(codomain)——注意不是值域——变为了状态集 $ Q $ 的超集 $ \mathcal{P}(Q) $ 。

除此之外,非确定自动机的转移函数还能接受输入 $ \varepsilon $ ,即在不接受任何输入的时候也可能随机发生转移。自动机在处于某个状态时接受某个符号会转移到一个唯一的确定状态,而处于某个状态的非确定自动机,接受某个符号的输入则会有一些状态构成的集合作为”候选”状态,它会随机地从这些状态中选择一个进行转移。

如果我们将非确定自动机的每一次转移视作它产生了几个并行的计算分支, 那么我们由如下图所示的描述:

左图为自动机的计算步骤,其每一步计算都是仅产生一个计算分支,而整个计算过程由一个计算分支过程,自动机是否判定某个串,取决于这个唯一的计算分支是否在串的输入结束后处于接受状态。我们同样将这一概念推广到非确定自动机上。

非确定自动机每一步都会产生多个计算分支,而整个计算过程的计算分支可能会非常复杂。它的整个计算过程可以用一个深度等于输入长度加 $ 1 $ 的树来表示,其每个节点都是一个非确定自动机的状态,而路径则是合法的转移。

通过这种方式,我们可以知道每一条根到叶子的路径都是一条计算分支。现在我们定义:如果非确定自动机 $ N $ 在输入 $ x $ 时存在一条计算分支在输入结束后处于接受状态,我们就说非确定自动机 $ N $ 接受输入 $ x $ , 记作 $ N(x)=1 $ 。否则我们称非确定自动机 $ N $ 拒绝串 $ x $ , 记作 $ N(x)=0 $ 。

例如下面的非确定自动机,处在 $ q_1 $ 状态时其可能会随机转移到 $ q_3 $ 状态。而当它处于 $ q_2 $ 状态并收到输入 $ a $ 时可能转移到 $ q_2 $ 或 $ q_3 $ 状态。

在模拟计算过程时,可以计算通过将每一步机器可能处于的状态视作一个集合(称之为合法状态集),并在收到某个输入符号时计算每个合法状态集中的状态对应该符号根据转移函数得到的状态集合的并集。例如下图中的非确定自动机根据输入 $ bc $ :

  1. 首先在起始状态时, 可能随机转移到状态 $ q_3 $ , 因此此时的合法状态集是 $ \{q_1,q_3\} $
  2. 在收到第一个输入 $ b $ 时, 状态 $ q_1 $ 只能转移到 $ q_2 $ , 而状态 $ q_3 $ 根据输入 $ b $ 无法转移, 因此这一步的合法状态集为 $ \{q_2\} $
  3. 在收到第二个输入 $ c $ 时, 状态 $ q_2 $ 无法转移, 因此这一步的合法状态集为 $ \emptyset $ .

因此该非确定自动机拒绝串 $ bc $ 。

如果熟悉并行计算,那么非确定自动机的计算步骤可以理解为”并行的”,即每一条计算分支相当于被非确定自动机并行的执行。需要注意的是,计算分支数很可能是无限多的,这样的机器在现实世界中不太可能被制造出来,但可以通过算法进行模拟。

非确定自动机的计算能力

从自动机与非确定自动机的定义可以看出,自动机是非确定自动机中很特殊的一类机器,相当于是机器处于任意状态时, 收到任意输入符号, 仅能转移到至多一个状态的非确定自动机。

现在我们通过建立一台指定任意非确定自动机 $ N $ 计算能力相同的自动机 $ M $ , 来说明,自动机和非确定自动的计算能力是相同的。

定理2

设 $ L $ 为语言,存在一台自动机 $ M $ 判定 $ L $ 当且仅当存在一台非确定自动机 $ N $ 判定 $ L $ 。

回想一下”合法状态集”,非确定自动机 $ N $ 处在某一步计算时接受另一个输入,可以视作从一个合法状态集转移到了另一个合法状态集,而一个输入是否被接受,取决于非确定自动机在该输入下最后一步计算对应的合法状态集中是否有接受状态,因此我们通过这一点将一台非确定自动机 $ N(Q, \Sigma_\varepsilon,\delta, q_0,F) $ 变为一台自动机 $ M $ 。

  1. 由于每一步计算都视为合法状态集到合法状态集的转换,因此 $ M $ 中的状态集是 $ Q $ 的超集,即 $ \mathcal{P}(Q) $
  2. 由于自动机不能发生随机转移,因此 $ \varepsilon $ 不能参与转移,即自动机的第二个参数退化为 $ \Sigma $
  3. 转移函数 $ \delta^\prime $ 是一个 $ \mathcal{P}(Q)\times \Sigma \to \mathcal{P}(Q) $ 的集合,显然这个转移是确定的,因为每一个 $ \mathcal{P}(Q) $ 中的元素都能够被 $ M $ 的一个状态表示。
  4. $ M $ 的起始 $ q_0^\prime $ 状态是 $ q_0 $ 及 $ q_0 $ 能随机转移到的那些状态构成的集合。
  5. $ M $ 的接受状态集是所有含有 $ F $ 中任意元素的集合的集合。

通过这样的转换, 我们容易证明, $ M(x)=1 $ 当且仅当 $ N(x)=1 $ 。

总计一下就是,我们可以通过”子集构造“的方式来证明 DFA 和 NFA 的计算能力等价。

正则语言与非确定自动机

令人惊奇的是,任何一个正则语言都能被一台非确定自动机判定,而任何一台非确定自动机判定的语言都是正则语言。本文不打算证明这一点(教材上的证明非常详细),但是会介绍一下如何将一个正则语言转换为判定它的非确定自动机。

定理3

一个语言 $ L $ 是正则语言, 当且仅当存在一台非确定自动机 $ N $ 可以判定它。

广义非确定自动机是非确定自动机的推广版本,它的定义和非确定自动机类似,唯一不同的一点在于其转移函数 $ \delta $ 表示的映射是 $ Q\times \Pi \to \mathcal{P}(Q) $ , 其中 $ \Pi $ 表示所有正则表达式的集合。

用通俗的语言来讲,它的状态集图上箭头的标号可以不仅是语言中的某个符号,而是可以是整个正则表达式。我们已经很清楚的知道,每个正则表达式确实就是表示了某个正则语言,因此广义非确定自动机的转移是在读取一个串后进行的。

根据一个正则表达式可以做出最原始的广义非确定自动机。例如对正则表达式 $ R $ ,我们可以作出状态机图 $ q_0\overset{R}{\to}q_1 $ 。其中 $ q_0 $ 是起始状态, $ \{q_1\} $ 是接受状态集。我们考虑正则语言的三种操作,将它表示转移函数中的正则表达式仅有最基础的三种正则表达式(即 $ \varepsilon $ , $ \emptyset $ , 单个符号 $ a $ )的广义非确定自动机(其中 $ \emptyset $ 标注的转移函数可以略去不写)。

现在尝试逐步将判定 $ R $ 的广义非确定自动机 $ G $ 化为非确定自动机 $ N $ 。首先,如果 $ R $ 是三种最平凡的正则表达式( $ \emptyset $ , 仅含一个单个符号的正则表达式, 正则表达式 $ \varepsilon $ )中的一种,那么 $ G $ 就已经是非确定自动机了。如果 $ R $ 是由两个正则表达式 $ R_1,R_2 $ 按照三种运算( $ \cup $ , $ \circ $ , $ \ast $ )组成的,那么我们按照以下方式处理:

  1. $ R=R_1\cup R_2 $ 只需要将下图中的左图转换为右图即可。如果左图中的 $ q_1 $ 是接受状态,则右图中的 $ q_{11},q_{12} $ 均为接受状态

  2. $ R=R_1\circ R_2 $

    只需将下图的左图转换为右图即可。如果左图中的 $ q_1 $ 是接受状态, 则右图中的 $ q_{12} $ 是接受状态.

  3. $ R=R_1^\ast $

    只需将下图中的左图转换为右图即可。

递归地进行以上三种操作,任何一个正则表达式都可以在有限步骤内转为为一台判定它的非确定自动机,因此我们证明了定理 $ 3 $ 。同时根据定理 $ 1 $ 我们有:

定理4

语言 $ L $ 是正则语言,当且仅当存在一台非确定自动机 $ N $ , 满足 $ x\in L\iff N(x)=1 $ 。

正则语言与自动机

根据定理 $ 2 $ , 一台非确定自动机总能够转换为一台计算能力和它相同的非确定自动机。因此, 根据定理 $ 4 $ 我们有

定理5

语言 $ L $ 是正则语言,当且仅当存在一台自动机 $ M $ ,满足 $ x\in L\iff M(x)=1 $ 。

泵引理

泵引理(pumping lemma)是一个用于判断一个语言是否为正则语言的引理。泵引理给出了一个语言是正则语言的必要非充分条件,我们不证明该引理,但是会对它做一些直观的解释,并且举例说明用它来证伪一个语言是正则语言。

假设 $ { L\subseteq \Sigma ^{*}} $ 是正则语言,存在字符串 $ { w\in L} $ 且 $ { \left|w\right|\geq n} $ ,则以下说法成立:

  1. $ { \left|xy\right|\leq n} $
  2. $ { \left|y\right|\geq 1} $
  3. $ { \forall k\geq 0:xy^{k}z\in L} $