Kleene定理

定理6(Kleene定理)
所有可以被

  1. 正则表达式
  2. 有限自动机
  3. 状态转换图

中的任意一种方法定义的语言,都可以被所有三种方法定义
该定理是有限自动机理论中最重要而又最基础的定理

Remark

  一般来说,为了证明集合\mathcal{A}等价于集合\mathcal{B},我们可以把证明过程分成两部分:

  1. 证明\forall_{a\in\mathcal{A}}(a\in\mathcal{B})
  2. 证明\forall_{b\in\mathcal{B}}(b\in\mathcal{A})

在Kleene定理中,我们需要类似的证明三个集合(可以被正则表达式定义的语言集合,可以被有限自动机定义的语言集合,可以被状态转换图定义的语言集合)是等价的,假设对于集合\mathcal{A}\mathcal{B}\mathcal{C},我们想要证明三者等价,可以类似的划分为三个部分:

  1. 证明\forall_{a\in\mathcal{A}}(a\in\mathcal{B})
  2. 证明\forall_{b\in\mathcal{B}}(b\in\mathcal{C})
  3. 证明\forall_{c\in\mathcal{C}}(c\in\mathcal{A})

简而言之,就是

[\mathcal{A}\sube\mathcal{B}\sube\mathcal{C}\sube\mathcal{A}]\equiv[\mathcal{A}=\mathcal{B}=\mathcal{C}]

类似的,对于该定理的证明也会被划分成三个部分

  1. 引理:所有可以被有限自动机定义的语言都可以被状态转换图定义
  2. 引理:所有可以被状态转换图定义的语言都可以被正则表达式定义
  3. 引理:所有可以被正则表达式定义的语言都可以被有限自动机定义

当我们分别完成对这三个引理的证明的时候,也就完成了对该定理的证明

引理1:所有可以被有限自动机定义的语言都可以被状态转换图定义

  该引理证明十分简单,因为每个有限自动机本身就是一个状态转换图,因此所有被有限自动机定义的语言本身已经被状态转换图所定义
Q.E.D.

引理2:所有可以被状态转换图定义的语言都可以被正则表达式定义

Remark

  我们通过构造性证明来证明该引理,也就是说,给出一个算法,输入是一个状态转换图,而输出是对应的正则表达式,要求该算法必须满足两点要求:

  1. 必须对于任意TG都起作用
  2. 必须在有限长的时间内停机

由于仅仅是证明引理的正确性,我们不需要考虑算法的优化等问题,只需要给出任意一个可行算法即可

  算法的第一部是对状态转换图做一些手脚,比如简化到只有一个起始状态和一个停机状态,这一步的实现很简单,仅仅需要添加一个新的起始状态和一个新的停机状态,并把旧的起始和停机状态都通过带有\varLambda的边连上去即可,比如对于TG1:

可以归约为

而对于

则可以归约为

注:以上四张状态转换图要么是没有起始状态,要么是没有停机状态,这里是为了省略考虑,只画出需要注意的部分,接下来也会这么做

如果该TG的起始状态和停机状态都是同一个,那么将会创建两个新状态链接到这个状态上,一个作为新的起始状态,一个作为新的停机状态,比如

转换为

接下来,我们将会把已经简化过的TG转换为一个GTG(详见上一章),对于GTG:

可以转换为

类似的,有

等价于

对于包含一个中间状态的三个状态,我们可以通过把中间状态转换为一个正则表达式来消去该状态,重复这个操作,就可以不停的消除掉多余的边,类比上面的两种,可以接着定义如下几种消去规则:

  1. 对于形如

    可以转换为

  2. 对于形如

    可以转换为

  3. 如果一个GTG存在多个状态,其中状态1连接到状态2,而状态2连接到多个不同的状态,则我们需要一条一条的分别消去这些边,例如

    可以转换为

    像这样,如果要消去状态2,就要把所有引向2的边都消去,也就是通过上面的正则表达式转换,来让他们直接引向状态2所引向的那些状态,一旦完成之后,状态2就没有任何输入边,也就是说任何经过该自动机的字符串都不可能进入状态2,此时就可以将状态2以及其输出边删除。

重复以上步骤若干次后,我们最终会得到一个GTG,其中只有起始和停机两种状态,没有其他任何状态,所有的边都连接了这两个状态并被标记上了一个对应该边所识别语言的正则表达式,也就是类似

的图,而要想让边只剩下一条,只需要用+连接每个边的正则表达式即可

要注意的是,为了保证整个机器接受的语言没有变化,我们必须对要消去的状态的每个输入边都做类似的处理,而不能仅仅对其中一部分的输入边做类似处理而忽视剩下的,因为我们不知道读取的字符串将会走哪一条路径;接下来让我们考虑一个消去规则中的特殊情况:

注意到在状态1和2之间形成了一个环路,再考虑该状况是可能有些棘手,但是针对类似问题的解决办法依然是循着概念出发,原先的GTG中,经过2的路径有两个,分别是3\rightarrow 2\rightarrow 11\rightarrow 2\rightarrow 1,也就是分别起始自状态3和状态1,并且都结束自状态1,因此我们需要建立状态3和状态1,以及状态1和状态1之间对应原先包含状态2路径的边,理清楚这两点后,就可以把原机器转化为

当然,也可以说路径是3\rightarrow 2\rightarrow 1\rightarrow 2\rightarrow 1,但是经过该路径产生的正则表达式对应的路径依旧可以被转化后的机器表示,因此“多绕点弯路”在这里并非问题。重申一次,当转换一个GTG的时候,必须确保以前可行的路径依然可行,以前不可行的路径依然不可行,应当注意到如果我们采用不同的顺序去消除各个中间状态,产生的正则表达式也将会是不同的,但是最终它们都将会代表同一种语言

证明

这里将会提供一种构造性的算法,用于从任意给定的TG生成对应的正则表达式

  1. 第一步,将原TG转换为一个拥有唯一起始和停机状态的新TG
  2. 第二步,一个接一个的消除掉所有并非起始状态和停机状态的状态,消去的方法是对于每个状态,找到这个状态的所有输入边所对应的状态以及所有输出边连接到的状态,并且在这些状态之间用一个新的边联系起来,这个新边对应的正则表达式是以前的几条边(以及中间状态对应的正则表达式,如果中间状态包含循环的话)的拼接,之后删掉中间的状态
  3. 第三步,当两个状态之间只由多个边连接,不包含任何中间状态的时候,创建一个新的边连接两者,并标记上由加号(+)连接所有其他边对应正则表达式的正则表达式,之后删掉所有其他的边
  4. 第四步,当上面的所有步骤都完成以后,TG应当只剩下一条连接起始和停机状态的边,这条边就是该TG所对应的正则表达式

这里可能存在一种该算法没有覆盖到的情况,也就是当执行完步骤3后,起始和停机状态之间没有任何边连接,在这种时候,我们说这个机器不接受任何字符串,而是仅仅接受语言\phi和由\boldsymbol{\phi}定义的语言。
  我们现在拥有了一个把任意TG转换为正则表达式的算法,并且保证该算法会在有限步内停机(因为每个TG最多只有有限个状态),因此证明完毕
Q.E.D.

引理3:所有可以被正则表达式定义的语言都可以被有限自动机定义

Remark

我们将通过递归定义和构造性算法证明这一点,针对正则表达式的每一条定义,我们描述一个算法,使得能够从该定义产生的正则表达式产生一个对应的有限自动机,当我们针对正则表达式的每一条定义都描述了一个算法后,也就完成了对于该引理的证明

引理1:存在一个有限自动机接受字母表中的任意字母,存在一个有限自动机接受空串

  这一步的证明非常简单,只需要给出两个对应的FA即可,分别是接受x\in\varSigma的自动机

和接受空串的自动机

Q.E.D.

注:接下来的三个引理证明比较晦涩,可以尝试自己一步一步的通过remark中的提示来画对应的状态转换图理解

引理2:如果存在FA₁识别由Γ₁定义的语言,FA₂识别由Γ₂定义的语言,则存在FA₃识别(Γ₁+Γ₂)定义的语言

Remark

  和之前证明任何TG都可以转换为正则表达式一样,这次同样使用构造性证明来根据两种正则表达式对应的FA来生成一个新的FA,也就是提供一个算法来构造一个有限自动机,使其既能接受FA₁接收的字符串,也能接受FA₂接收的字符串
  依旧和之前一样,在描述具体的算法前,先通过描述几个具体的例子来解释算法是如何执行的,假设我没有这样的一个自动机FA₁,接受\varSigma=\lbrace a,b\rbrace上的语言\mathcal{L}=\lbrace \text{所有包含两个a的字符串}\rbrace:

以及其对应的状态转换表2

\begin{array}{c:cc}
& a & b \\ \hline
-x_1 & x_2 & x_1 \\
x_2 & x_3 & x_1 \\
+x_3 & x_3 & x_3
\end{array}

在给出另外一个FA₂,识别之前提到的\varSigma=\lbrace a,b\rbrace上的语言EVEN-EVEN,该语言中的单词包含偶数个a和偶数个b

以及其状态转换表

\begin{array}{c:cc}
& a & b \\ \hline
\pm y_1 & y_3 & y_2 \\
y_2 & y_4 & y_1 \\
y_3 & y_1 & y_4 \\
y_4 & y_2 & y_3
\end{array}

接下来我们将会一步一步的构造接受\mathcal{L_2}=\mathcal{L}\cup EVEN-EVEN的有限自动机FA₃,并把FA₃中的新状态叫做z_1z_2z_3,...,鉴于很明显的原因,我们将会使用状态转换表而非图的形式来一个个描述状态之间的关系
  FA_3中的每个状态都应当包含双重含义,也就是既包含FA_1中对应状态的含义,也包含FA_2中对应状态的含义。首先让我们定义z_1z_1既代表了FA_1中的起始状态,又代表了FA_2中的起始状态,同时,因为x_1是起始状态而y_1是停机状态,所以z_1包含的两种含义叠加起来,也就是z_1既是起始状态又是停机状态,然后观察,在z_1时读取一个a会发生什么,如果在FA_1上,状态会转换到x_2,如果在FA_2上,状态会转换到y_3,也就是:

\begin{aligned}
\pm z_1&=x_1\ or\ y_1 \\
z_2&=x_2\ or\ y_3
\end{aligned}

接下来再考虑,如果我们在z_1时读入一个b,会发生什么,根据状态转换表,对于FA_1会保持x_1,而对FA_2则转换到状态y_2,也就是

z_3=x_1\ or\ y_2

接下来考虑在z_2时读入一个a的情况,对于FA_1,是x_3,而对于FA_2则是y_1,注意x_3是一个停机状态,因此z_2也应当是一个停机状态,接着考虑读入b,对于FA_1x_1,对于FA_2y_4,也即

\begin{aligned}
+z_4&=x_3\ or\ y_1\\
z_5&=x1\ or\ y_4
\end{aligned}

一直重复这个过程下去,我们可以得到一个完整的状态转换表:

\begin{array}{c:cc}
& a & b \\ \hline
\pm z_1 & z_2 & z_3 \\
z_2 & z_4 & z_5 \\
z_3 & z_6 & z_1 \\
+z_4 & z_7 & z_8 \\
z_5 & z_9 & z_{10} \\
z_6 & z_8 & z_{10} \\
+z_7 & z_4 & z_{11} \\
+z_8 & z_{11} & z_4 \\
z_9 & z_{11} & z_1 \\
z_{10} & z_{12} & z_5 \\
+z_{11} & z_8 & z_7 \\
+z_{12} & z_7 & z_3
\end{array}

为什么我可以这么确定一共有12种状态?简单的排列组合呀,FA_1一共3个状态,FA_2一共4个状态,如果无序且不包含重复的话,自然一共就有12个状态,此时的FA应该长这个样子,看上去非常庞大:

如果字符串s被该自动机接受,则说明字符串s要么被FA_1接受,要么被FA_2接受,到此为止,我们会发现可以通过把类似的操作应用在任意两个FA上,来给出一个算法

证明

  我们将会给出一个算法,证明对于任意接受\footnotesize \varGamma_1\footnotesize \varGamma_2的自动机FA_1FA_2,存在一个自动机FA_3接受(\footnotesize \varGamma_1+\footnotesize\varGamma_2)

ALGORITHM
对于拥有状态x_1,x_2,x_3,...并接受由\footnotesize \varGamma_1定义的语言的有限自动机FA_1和拥有状态y_1,y_2,y_3,...并接受由\footnotesize \varGamma_2定义的语言的有限自动机FA_2,给出拥有状态z_1,z_2,z_3,...的有限自动机FA_3,其中每个z都包含FA_1FA_2中对应状态的两重含义,如果对应的任意一个状态是起始或者停机状态,那么该z状态也是起始或停机状态,由x_1y_1(这里假设这两者分别是FA_1FA_2的起始状态)构成的状态z_1将会是FA_3的起始状态,从一个z状态出发读取一个字符p,我们将会得到新的状态

z_{new}=FA_1中读取p之后的状态x_p或者FA_2中读取p之后的状态y_p

因为FA_1FA_2所拥有的状态数都是有限多个,因此最终FA_3的状态数也必定是有限多个,至此,我们给出了对应算法的构造方法。
Q.E.D.

引理3:如果存在FA₁识别由Γ₁定义的语言,FA₂识别由Γ₂定义的语言,则存在FA₃识别Γ₁Γ₂定义的语言

Remark

  依然是从例子出发,给出两个FA,一个接受包含两个连续的a的字符串,另一个接受以b结尾的字符串

从定义出发,因为根据定义,Γ₁Γ₂定义的语言就是

language(\footnotesize \varGamma_1\footnotesize \varGamma_2)=\lbrace \forall_{x\in language(\footnotesize \varGamma_1)}\forall_{y\in langauge(\footnotesize \varGamma_2)}\vert xy \rbrace

因此要想构造接受\footnotesize \varGamma_1\footnotesize \varGamma_2的FA,我们必须先让该FA接受对应\footnotesize \varGamma_1的部分,然后接受对应\footnotesize \varGamma_2的部分
和上面证明引理2时一样,令FA_3的状态为z_1z_2z_3,...,有

z_1=x_1\\
z_2=x_2

FA_3的前半部分和FA_1的前半部分一模一样,因为就如同之前所说的,我们要让FA_3先接受FA_1接受的部分:

现在,如果FA_3读取字符串并转移到了状态z_2,然后再读一个a,并把FA_3中对应的状态叫做z_3,那么根据图示,FA_1此时会转移到x_3状态,然而x_3是一个停机状态,同时又有输出边,此时我们就需要决定,当前的状态到底是代表应该结束FA_1中的流程并进入FA_2,还是说x_3仅仅是一个中间状态,并非该字符串在FA_1中真正的停机状态,也许该字符串还要在被读取若干次,也就是在x_3状态的循环上循环若干次,才会真正的在x_3上停机,因此,z_3在这里就包含了两重含义,两种可能:

z_3=
\begin{cases}
x_3,该字符串并非真的已经在FA_1停机,x_3只是作为一个中间状态\\接下来还要继续在FA_1上运行\\
y_1,该字符串已经在FA_1上运行到停机状态,接下来应该转移到FA_2\\上运行,以此来接受该字符串接下来的那部分\\
\end{cases} \\

如果此时再去读一个a,就又多了一种可能,也即在y_1状态上循环了一次:

\begin{cases}
x_3,该字符串并非真的已经在FA_1停机,x_3只是作为一个中间状态\\接下来还要继续在FA_1上运行\\
y_1,该字符串已经在FA_1上运行到停机状态,接下来应该转移到FA_2\\上运行,以此来接受该字符串接下来的那部分\\
y_1,该字符串在FA_2的y_1状态上循环了一次,又回到了y_1\\
\end{cases} \\
\begin{aligned}
&= x_3\ or\ y_1\\
&= z_3
\end{aligned}

上面的三条归约一下,第一条相当于状态x_3,第二和三则都相当于y_1,也就是再去读一个a后的状态依旧是x_3或者y_1,即上面总结过的z_3所代表的状态。如果我们在z_3的状态下读一个b,那么对于FA_1,依旧是在x_3上循环,或者已经停机,开始进入FA_2的第一个状态y_1,而对于FA_2,唯一的可能就是通过y_1和标记了b的边转换到状态y_2,因此读了一个b后,状态是如下的,我们把它命名为状态z_4

+z_4=
\begin{cases}
x_3,该字符串并非真的已经在FA_1停机,x_3只是作为一个中间状态\\接下来还要继续在FA_1上运行\\
y_1,该字符串已经在FA_1上运行到停机状态,接下来应该转移到FA_2\\上运行,以此来接受该字符串接下来的那部分\\
y_2,该字符串在y_1读取了一个b,因此转移到了y_2
\end{cases}

注意,z_4中包含了状态y_2,而y_2是一个停机状态,这意味着如果字符串在FA_3的状态z_4处结束,代表其前半部分首先被FA_1所接受,然后后半部分又被FA_2所接受,是引理中提到的\footnotesize \varGamma_1\footnotesize \varGamma_2所定义的语言,同时又已经被两个FA所接受,因此FA_3也应当在这里接受这个字符串,这蕴含着z_4必须是FA_3的停机状态,继续按照同样的方法推导接下来的状态,会发现在z_4无论读取a或者b都会回到已有的状态,因此推导结束。实际上这里的FA_3一共有四个还是可以提前得出的,因为FA_1FA_2一共有五个状态,而FA_3在功能上相当于把FA_1FA_2首尾相连,并且共享一个状态(FA_1的停机状态同样是FA_2的起始状态),因此算下来,FA_3一共有四个状态,此时的FA_3如图

到此为止,我们已经用接受语言\footnotesize \varGamma_1FA_1\footnotesize \varGamma_2FA_2构建了接受语言\footnotesize \varGamma_1\footnotesize \varGamma_2FA_3

证明

  我们将会给出一个算法,证明对于任意接受\footnotesize \varGamma_1\footnotesize \varGamma_2的自动机FA_1FA_2,存在一个自动机FA_3接受\footnotesize \varGamma_1\footnotesize\varGamma_2

ALGORITHM
FA_1的状态是x_1x_2x_3,...,FA_2的状态是y_1y_2y_3,...,FA_3的状态是z_1z_2z_3,...

  1. 对于FA_1中的所有非停机状态,构建一个对应FA_3中的状态z_n,对于x_n,这些z_n表达的意义和x_n完全等价
  2. 对于FA_1中的所有停机状态,构建一个对应FA_3中的状态z_n,该状态包含两种不同的含义
    1. 该状态虽然是停机状态,但是字符串并未结束在FA_1上的运行,只是一个中间状态,因此对应的状态根据FA_1上该状态的下一个状态决定(这种情况会出现仅当该停机状态有输出边,也就是字符串可以从这个停机状态逃逸出去)
    2. 字符串在FA_1的该状态上停机,转移到FA_2y_1上继续运行
  3. 对于对应FA_2部分的所有状态,都包含
    1. 一个FA_1x状态的可能性,因为可能字符串还在FA_1还在继续运行
    2. 一个FA_2中的任意y状态的可能性
  4. FA_2的任何停机状态对应到FA_3中也是停机状态

  当对于字符串的读取进入FA_2的部分后,每个z_n就至少代表了一个FA_1中的一个状态,也就是每个z_n至少代表一个x,而对于FA_2的部分,则应当注意,对于z_n来说,其包含的那个在FA_1中运行的可能性也许会停机并且跳到y_1状态,因此对于每个属于FA_2z_n,都有一个y_1的可能,但是因为从FA_1跳转到y_1的节点不同,因此这些y_1对应的是字符串的不同位置,也就是FA_2对应的z_n都有代表y_1的可能,但是却是在字符串的不同位置,正因如此,他们接下来对应FA_2中的y状态也会根据真正对应y_1的那个z_n在状态转换图上和其他状态的关系而决定,也就是说,每个对应FA_2部分的z_n中都可能对应了任意的y状态。由于当字符串运行到FA_2部分也就代表只剩下属于FA_2定义的语言的部分需要被接受,因此所有FA_2中对应的停机状态,也都应当是FA_3的停机状态。
  很明显的,因为FA_1FA_2都只有有限多个状态,因此FA_3也一定只有有限多个状态,并且拥有一个唯一的起始状态,也就是对应FA_1x_1z_1,而状态转移本身是唯一的,一个状态根据某个读入字符只会转移到一个特定的状态上,因此FA_3是一个良定义的有限自动机,证明完毕。3
Q.E.D.

引理4:如果存在FA₁识别由Γ₁定义的语言,则存在FA₂识别Γ₁*定义的语言

Remark

  由\footnotesize \varGamma^\ast定义的语言一定包含空串\varLambda,因此对应FA_2的起始状态必须同样也是停机状态,但是这可能会直接导致整个机器的语义发生变化,因为原先FA_1中回到起始状态的那些路径可能是不应当被接受的,而现在起始状态被标记为停机状态后,它们就可以被接受了,这会让对应FA_2识别的语言不再是\footnotesize \varGamma^\ast,因此不能通过简单的把两个自动机的首尾相连来做到这点。
  同样从例子出发,首先构造一个\footnotesize \varGamma=a^\ast+aa^\ast b对应的FA_1,该正则表达式代表了所有由空串或仅a或以b结尾并且左侧有至少一个a所构成的字符串,对该正则表达式取闭包得到的是\footnotesize \varGamma^\ast=(a^\ast+aa^\ast b)^\ast\footnotesize \varGamma\footnotesize \varGamma^\ast显然是不同的,因为\footnotesize \varGamma不允许abaaaa,但是\footnotesize \varGamma^\ast却允许,我们先贴出FA_1

  和以前的方法一样,对于每个FA_1中的x状态,我们分析出对应FA_2中的z状态,首先对于z_1,很明显他应当代表x_1,因为字符串被读取的流程在这里出发,注意x_1既是停机状态又是起始状态,因此z_1也应当这样,如果我们在z_1读取一个b,也就相当于在x_1读取一个b,将会进入到x_4(注意x_4是一个无限循环,进去之后字符串就不可能再被接受),因此z_2等价于x_4,如果我们进入到状态z_2,字符串就毫无疑问的被拒绝了,原因很简单,因为对应的x_4一旦进入状态就会像被黑洞吸进去一样,再也没有到达停机状态的希望了。

\begin{aligned}
\pm z_1&=x_1 \\
z_2&=x_4
\end{aligned}

如果在z_1位置读入一个a,那么情况就要稍微复杂一些了,按照FA_1的图示,在x_1的位置读取一个a后会进入x_2,而x_2是一个停机状态,因此在接受\footnotesize \varGamma^\astFA_2中,这个状态就有了两层含义,第一是到了这个状态就代表读完了一个\footnotesize \varGamma,该去接受下一个\footnotesize \varGamma,也就是直接跳回x_1了。第二种是当前仅仅读了一个\footnotesize \varGamma的其中一部分,还要继续读下去,也许可能要再经过数次x_2才会停机(最典型的情况就是对于字符串aaaaa,要在x_2上“三过家门而不入”,第四次到达x_2时才会停机),此时对应的状态也就是x_2本身。因此,z_1读一个a对应的状态z_3也有两层含义,并且因为其中的一个可能性x_2是停机状态,因此z_3也应当是一个停机状态。注意,尽管z_3同样代表了起始状态x_1,但是这里的z_3却不能是起始状态,因为有限自动机定义要求有且仅有一个起始状态,之前我们已经令z_1为起始状态了,这里的z_3就不可能是另一个起始状态。

+z_3=x_1\ or\ x_2

  在对于z_3的处理中应当发现一点,每当走到FA_1中的一个停机状态,我们都有两种可能,第一种是继续执行下去,第二种是直接跳回x_1开始重新识别下一个子串。现在观察,在z_3读取一个a会是什么结果,如果对应状态是x_1,状态会转移到x_2,因为x_2本身是一个停机状态,所以还可以直接跳转回x_1;如果是x_2,则根据FA_1所示,只需“停在原地”,也就是依然待在x_2,因此z_3读取一个a最终的结果是x_1x_2x_2,简化一下就是x_1x_2,也就是z_3
  如果在z_3的位置读入一个b,那么对应状态x_1时会转移到x_4;对应状态x_2时转移到x_3,因为x_3本身是停机状态,因此同样也可以跳转回x_1。也就是说

+z_4=x_4\ or\ x_3\ or\ x_1

(注意为什么z_4是停机状态,因为x_3是一个停机状态)

  如果在z_4读入一个a,状态变成x_1或者x_2或者x_4(可以自行验证)

+z_5=x_1\ or\ x_2\ or\ x_4

z_5无论读入a或者b,都会回到已有的状态z_5z_4,因此到此为止FA_2的所有状态都已经被描述出来了,对应的自动机如下:

看上去上面的方法已经非常完善,但是实际上它有一个致命的缺陷,注意在上面这个例子原先的FA_1中,x_1既是停机状态又是起始状态,因此对应的z_1也既是停机状态又是起始状态,所以FA_2才能恰好接受\varLambda,那么如果原先的FA_1的起始状态仅仅就是一个起始状态,而并非停机状态,又该怎么做呢?(实际上此时,FA_1接收的恰好是\footnotesize \varGamma^+)
  在我脑中最先出现的是一个非常简单的想法,我们只需要强行把他标记为停机状态,不就可以接受\varLambda了吗?虽然这样做的确可以接受\varLambda,但是它同样引入了其他的问题,考虑这样的一个FA

该FA中唯一的停机状态是x_2,如果一个读入字符串最终停在x_1上,则该字符串应该是被拒绝的,但是如果我们简单的直接让x_1变成停机状态,那么原先不被接受的字符串,也就是停在x_1的那些,现在就可以被接受了,换言之可以说让x_1变成停机状态后这个FA就可以接受任意语言了,而这显然与原自动机识别的语言不符。
  解决这个问题的其中一个办法非常简单,我们知道如何构造一个只接受\varLambda的自动机,也知道如何构造上面所描述的自动机,根据引理2,我们可以直接把他们两个"加"起来,也就构造了一个接受\varLambda\footnotesize \varGamma^+的自动机。第二种办法,是我们把原先的x_1“分化”一下,扩展成两个状态:其一,是状态z_1,代表了起始状态x_1和停机状态;其二,是z_2,代表了起始状态x_1,而不代表停机状态。并且把z_1连接到原先的起始状态所连接到的状态上(可能包括起始状态本身)。之所以这么做的原因,就是避免之前提到的,原本不应当在x_1处被接受的语言被接受,现在它们可以选择前往z_2,因为z_2同样代表了起始状态,但是却不代表停机状态,比如,对于上面所示的FA,我们让x_1变成这个样子

在这里x_1按照上面的方法被分成了两个,z_1z_2,接着再去继续上文中提到的过程,在x_1b时,我们进入状态x_2,注意x_2是停机状态,因此也包含立即跳转回x_1的可能,也就是我们的新状态z_3=x_1\ or\ x_2,如果读取的是a,则会转移到z_2,也就是那个代表了非停机状态的x_1的状态。在z_2如果读取一个a,则会依旧待在z_2(别忘了z_2代表的是x_1),而读b则会和z_1一样来到z_3,而在z_3读取无论a还是b都会无外乎的回到z_3,因此整个描述了原FA的闭包的FA*就是这样的:

到此为止,我们已经完整的描述了从识别\footnotesize \varGamma的有限自动机构造识别\footnotesize \varGamma^\ast的自动机的算法。

证明

  我们将会给出一个算法,证明对于任意识别\footnotesize \varGamma的有限自动机FA_1,我们可以构造一个有限自动机FA_2识别\footnotesize \varGamma^\ast

ALGORITHM

  1. 对于FA_1的状态集合\mathcal{S},创建一个新的状态集合S_1=\mathcal{P}(\mathcal{S}),也就是说S_1中的每个状态都有多个原先S中的状态的可能性,然后从S_1中移除掉所有包含停机状态但不包含起始状态的可能性的状态
  2. 对于剩下的每一个非空状态p(也就是包含原S中的状态可能性数量不是0的状态),从p出发分别画两条a边和一条b边(注意我们默认使用的语言字母表只包含这两个字母),连接到另一个状态st,其中s包含的所有可能性恰巧是p中的每个可能性读了a之后对应的属于\mathcal{S}中的状态的集合,而t中的所有可能性恰巧是p中的每个可能性读了b之后对应的属于\mathcal{S}中的状态的集合
  3. 创建一个新的状态,这个状态既是起始状态又是停机状态,同时把这个状态用a边和b边分别连接到FA_1中的起始状态对应的边连接到的状态上(这一点参考上面最后一个例子中的x_1分化为z_1z_2),注意原先的起始状态的输出边可能连接到他自身,这种情况下新的状态也连接到旧起始状态自身
  4. S_2=\lbrace \forall_{x\in\mathcal{S_1}}\exists_{p\in x}(p\in \mathcal{S}\land p是一个停机状态)\vert s \rbrace中的所有状态都设置为停机状态

到此,我们给出了完整的算法,证明结束
Q.E.D.

非确定有限自动机

下一篇文章


  1. Mermaid.js无法描述拥有多个起始状态的状态转换图,因此,在本文以及下文中都将会在拥有多个起始或停机状态的图中使用s前缀标记起始状态,f前缀标记停机状态 ↩︎
  2. 和以前说过的那样,这里使用减号(-)表示起始状态,使用加号(+)表示停机状态 ↩︎
  3. 才学疏浅,水平有限,我实在是没有办法挖掘出汉字强大的表现力,来让这段文字显得更加浅显易懂,如有不满多加包涵 ↩︎

乱我心者,今日之日多烦忧