NFA与DFA的等价性(上)在线视频

同学们

在上一节我们讨论了DFA

对于同一个输入

从同一个状态出发

只能有一个转移

但是实际问题是这样子的

状态的转移并不唯一

能否修改DFA

使它对同一个输入

从同一个状态出发

可以有零个 一个或者是多个转移呢

从而既得到一个更为紧凑的

而且更容易设计的自动机

这一节我们将讨论的是

非确定的有穷状态自动机

从这个状态转换图我们可以看到

NFA对于同一个输入符号

从一个状态出发可以有零个

一个或者是多个转移

在q0状态下

接收输入字符0

状态要么停留在q0

要么转移到了q1状态

那么不确定的有限状态自动机

是如何识别单词的呢

NFA识别字母表上面的符号串t

它的过程和DFA是很相似的

也就是说对于字符串t

如果存在一条从某个初态

到某个终态的路径

而且这条路上所有的弧的标记字

依序连接成的串等于t

那么就可以说t可以被这个

有穷状态自动机接收或者是识别了

我们来看一下

M1是怎样接收00101的

按照上一节对FA的建模

输入带上面现在存放的就是00101

q0状态下

读头读取到了0

状态可能会转移到q0或者是q1

读头后移

读取到了0

如果当前的状态是q1

识别工作将无法继续

如果当前的状态是q0

状态将转移到q0或者是q1

读头继续后移

读取到了1

q0状态下面输入1

状态将停留在q0

q1状态下面输入1

状态将迁移到终态q2

读头继续后移

读取到了0

如果当前的状态是q0

状态将转移到q0或q1

如果当前的状态是q2

识别工作将无法继续

读头继续后移

读取到了最后一个字符1

如果当前的状态是q0

那么状态将转移到q0

如果当前的状态是q1

状态将进入终态q2

至此 读取字符串的工作就结束了

我们发现对于字符串00101来说

的确存在一条从初态q0

到终态q2这样的路径

那么00101是可以被M1接收的

如果说不确定有限状态自动机

它的某些结点既是初态又是终态

或者存在一条从某个初态

到某个终态的路径

它上面的弧被标记为ε

那么ε就可以被这个M所接受

对照DFA

我们可以给出NFA的形式化定义

NFA也是一个五元组

S是一个有限的状态集合

它的每个元素称为一个状态

∑是一个有穷的字母表

它的每个元素称为一个输入字符

f是序偶Sx∑*到S状态的多值映射

也称之为状态转移函数

Q∈S状态集

是一个非空的初态集

Z∈S状态集

是一个终态集

我们可以发现

相比DFA来说

NFA有一些非常突出的特征

首先 它有若干个初始状态

其次 状态转移函数

它是一种多值映射

而且它可以允许接收字和空字符ε

那么我们来看一下

带有空转移的NFA

NFA是允许接收ε输入的

也就是说

这种状态的跳转是可以同时进行

而不需要输入任何字符

我们来对照一下接收语言L的

这两个有穷状态自动机

那么在等价的前提下

相对于左边的DFA

右边的带空转移的NFA

显得更加的简洁

而且也更加智能

我们来比较一下NFA和DFA

NFA和DFA都是正则语言的识别模型

从定义的角度来看

对于一个输入字符

NFA可以进入若干个状态

而DFA只能进入唯一的一个状态

我们可以把DFA

看作是一种特殊的NFA

从处理的角度来看

NFA更加的智能

因为它具备同时处理

多个状态的能力

同时也具备对输入进行预测的能力

从时间的状态角度来看

NFA在某一个时刻

同时进入了若干个状态

但是 这若干个状态合在一起

它的“总效果”相当于

处于一个“综合状态”

我们可以让DFA的一个状态

去对应于NFA的一组状态

要说明的一点是

虽然DFA和NFA都能识别正规语言

但是他们之间存在着

时空权衡的问题

首先DFA编程容易实现

但是构造起来很难

可能比等价的NFA占用更多的空间

NFA虽然在构造起来很容易

但是编程的时候容易出现回溯

能否找一个从NFA到DFA

自动转换的算法呢

对于任意的NFA

其实都存在一个等价的DFA

那么从NFA到DFA的转换

它的主要思想就是去消除不确定性

究竟有哪些不确定性呢

首先NFA当中存在非常多的初始状态

我们可以合并初始状态集

成为一个状态

譬如在下面的这个例子当中

我们可以引入新的状态X

作为新的NFA的初始状态

然后从X向原来的NFA的

每个初始状态引ε弧

这样的话

就把所有的初态集成为一个初态

其次就是ε边

怎样消除ε边呢

这些ε的跳转可以同时进行的

无需输入任何的符号

那么我们也可以将这些状态

看成为等价的状态

大家可以看到

在这个例子当中

我们可以将状态4和5合为一个状态

最后就是多重定义的边

我们可以消除多重定义的边

例如从状态6射出两条a边

分别去了状态7和状态8

那么就可以将状态7和8

看做是一个状态

这样也就消除了多重定义的边

从NFA到DFA的转换

我们也称为NFA的确定化

为了实现NFA确定化的任务

首先是状态集合I的ε闭包

表示为-closure(I)

那么它定义为这样的一个状态集

也就是说从状态集I当中的任何状态S

经过任意条ε弧而能够到达的

状态的集合

如果q∈I的话

那么q∈-closure(I)

如果q∈I

那么从q出发经过任意条ε弧

而能到达的任何状态q'

也属于-closure(I)

我们来看这个例子当中

集合I的状态是1

那么ε-closure(I)

除了状态1之外

还包含从状态1出发

经过ε弧

所到达的状态2

如果集合I当中的状态是5

那么ε-closure(I)

除了状态5之外

还包括从状态5出发

经过ε弧

所到达的状态6和2

其次是状态集合I的a弧转换

表示为move(I,a)

定义了状态集合J

其中J是那些可以I当中的某一个状态

经过一条a弧

而能够到达的状态的集合

那么用它来定义Ia

Ia = ε-closure(J)

我们来看在这个例子当中

假设状态I= ε-closure(1)

它所得到的状态集合是1和2

从状态1和2出发

沿着a弧

能够找到的状态集5 4 3

Ia就是5 4 3的ε闭包

得到的结果就是{5,4,3,6,2,7,8}

在这一节当中

我们通过NFA和DFA的对比

给出了NFA的形式化定义

也看到了带有空转移的NFA

为了完成从NFA到DFA的转换

消除不确定的因素

我们学习了两个非常重要的定义

就是I的ε闭包和Ia

下节课我们将利用这两个

非常重要的定义

通过子集法来完成NFA的确定化工作

这节课就到这里

谢谢大家