非确定有限自动机

提示:这一章是第七章的一个小结,但是由于上一张的图表实在是过多了,导致在我的浏览器上阅读起来帧数有明显下降,因此把一部分笔记转移至新文章(多水一篇blog不存在的)

  非确定有限自动机,或者叫做NFA,是一种和TG一样拥有非确定性,但是却要比TG更常用的一种模型

定义

  非确定有限自动机(Nondeterministic Finite Automata),或者非确定有穷自动机,是状态转换图(TG)的一种,它的各个定义都与TG类似,除了要求非确定有限自动机有且仅有一个起始状态,并且每条边都只能被标记一个字母表中的字符(TG允许标记一个字符串),非确定有限自动机可以被缩写为NFA,为了区分起见,普通的有限自动机将会被称为确定有限自动机(Deterministic Finite Automata),缩写为DFA1

笔记

  NFA既具备TG的一部分特征,也具备DFA的一部分特征,它有一个唯一的起始状态,并且每条边都只能标记一个单独的字符,这符合DFA的特征;但同时它从一个状态出发又可以有多个标记了相同字符的边,并且每个状态可以派生出多个,或者0个边,这些则都是TG的特征,比如如下就是一个NFA

  NFA的一个(不那么重要的)应用是消除某些状态自身上的循环,比如对于

可以通过创建一个与状态4对应的状态4',并让他们构成一个环路来去掉状态4上面的循环

NFA=DFA

  在这一章的上一部分,我们展示了任何TG都可以被转换为DFA,而NFA是一种TG,因此所有的NFA也都可以被转换为DFA,在接受语言的范围上,NFA=DFA

定理7

  对于所有NFA,都存在至少一个DFA接受同样的语言

证明

  算法毫无疑问是存在的,只需要用Kleene定理中的第二部分,把NFA转换为正则表达式,在根据第三部分把正则表达式转换为DFA即可,但是这种算法效率实在是太低了,因此我们采用另一种算法。
  这个算法同样很简单,类比把FA转换成FA*的算法,令NFA的状态是x_1x_2x_3,...。其中x_1是起始状态,那么可以同x_1开始构造对应的DFA,令z_1=x_1,也即起始状态。其中DFA的每个状态z_n代表了一个x状态的集合,而z_{n+1}所代表的x的集合就是\lbrace x\in z_n\vert\text{state after read an a on x}\rbrace\cup\lbrace x\in z_n\vert\text{state after read a b on x}\rbrace,因为在NFA中,每个状态不一定要派生对应字母表中所有字符的边,比如可以选择只派生a边,也可以选择只派生b边,甚至可以选择不派生任何边,而如果在不派生a边的状态上读入a,NFA就会崩溃,相对于b边同样如此,因此在DFA中,对于这些没有派生的边,需要让他们连接到一个无限循环,再也没法出去的状态,在这里一直循环到字符串被读取完毕,之后被DFA拒绝,这个状态我们叫做\phi状态,该状态将会对字母表中的所有字符(这里的例子是ab)派生出一条边并且回到自身,这样就可以保证所有进到该状态的路径都永远无法再出去;最后,我们再把DFA中所有包含了原先NFA中停机状态的状态标记为DFA的停机状态即可。

  比如对于NFA

对应的DFA是

利用NFA证明Kleene定理

  利用NFA可以简化之前对于Kleene定理的证明,例如引理1要求证明存在DFA识别单个字符,和存在DFA识别空串,那么通过构造对应的NFA,加上之前证明的所有的NFA都可以转化为DFA,就可以证明引理1,对于引理2的第二条,要求证明对于识别\footnotesize \varGamma_1DFA_1和识别\footnotesize \varGamma_2DFA_2,存在一个识别(\footnotesize \varGamma_1+\footnotesize \varGamma_2)DFA_3,我们可以通过如下算法来先构造NFA,再转换成DFA:
首先引入一个新的起始状态z_0,把这个状态连接到DFA_1的起始状态x_1DFA_2x_2,然后去掉x_1y_1的起始状态标记(也就是让他们不再是起始状态),接着照常的从x_1y_1画出DFA_1DFA_2对应剩下的部分即可,停机状态也保持原样不变,这样就构造出了一个对应(\footnotesize \varGamma_1+\footnotesize \varGamma_2)DFA_3的NFA,接着根据上面提到的算法,将其转换为DFA即可。


  1. 非确定有限自动机在1959年被Michael Oser Rabin和Dana Scott发明 ↩︎

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