Video在线视频

欢迎同学们来到《软件理论基础》的MOOC课堂

现在我们介绍

非确定有限自动机的定义

在上两节里面

我们给出了非确定有限自动机的基本概念

它们对一个输入字母

可以有多个转移 可以没有转移

而且还有ε转移

那对这样的自动机

我们怎么去给出它的形式化定义

或者是这个非确定有限自动机的

它的模型

那按我们的非确定有限自动机里面

我们有哪些基本要素呢

我们看

在我们的非确定有限自动机里面

它有状态 有输入字母

有状态转移函数

还有初始状态 也有终态

实际上它也是一个五元组

Q我们把它表示成

有限个状态构成的集合

输入字母用∑表示

但是在我们这里NFA里面

它可以用ε输入

状态转移函数我们用δ表示

开始状态是q0

终态或者结束状态是一个集合

我们用F表示

在这里强调一下

q0是状态集合当中的一个状态

而F是状态集合当中的一个子集

这些跟我们前面讲的

DFA的定义很类似

也是一个五元组

也是这么给出来的

但是这里面我们发现了

它的状态转移函数

跟我们的DFA是不一样的

这里面我们说不一样

从这个表示式里面大家可以看出

这里面的输入字母可以是ε

它的映射的相极

是状态的幂集合

而状态的幂集合 它实际上

包含有两种情况

要么这个里面是空集

也就是说它没转移

要么这个里面

是多个状态构成的集合

那就是有多个转移

所以我们说这个与DFA

它应该有三处不同 或者说两处不同

有状态转移图可以刻划DFA

还有状态转移表 也可以刻画的DFA

那在NFA里面 也有这些表示

像这一个自动机大家看

它的输入字母是0，1

你比如说在p这个状态里面

输入0 它是有转移的

但是输入1 它是没有转移的

在q这个状态呢

它输入0是有个自环

输入1 它就有一个自环或到r一个转移

而这里就有两个选择了

在r这个地方 它没有任何转移

所以这就是一个NFA

我们把它写成

另外的一种表示形式 状态转移表

我们依然第一列表示状态

第一行表示它的输入字母

这跟我们原来的DFA是一样的

而DFA的状态转移表呢

是对每一个状态 每一个输入字母

它必须要有一个转移

而且只有一个转移

也就是说这个表里面

它必须填满

而我们在NFA里面

它的转移就不是单个单个的状态了

因为我们的转移是一个幂集合

你像p输入0

它转移是状态q

那是一个状态

那是转移到q这一个子集

在p这个地方 输入0 它有转移

那输入1 它没有转移

那我们在没有转移的时候

我们就把它写成为空集

空集也是幂集合当中的一个元素

在q这个地方输入0

它转移到自己单个的q0

那如果输入1 它就有两个转移了

一个是q 一个是r

所以这个集合是包括q和r

在状态r输入0 它没有转移

输入1 它也没有转移

在第一列这个状态里面

我们依然

这个初始状态这里

用这个单个箭头来表示的

而终态这个地方是用*来表示的

所以这些表示形式

跟我们前面讲的DFA是很类似

这说明NFA也可以用状态转移表来表示

下面我们再看另外一个例子

这里也是一个NFA

它也可以按这种规律

把它的状态转移表把它写出来

第一列是它的状态

第一行是它的输入字母

那我们对每一个状态

对每一个输入字母

它转移的这是状态集当中的子集

我们都把它表示出来

这个就是它对应的

这个NFA的状态转移表

好 我们下面再看一个例子

这里也是一个NFA的状态转移图

它有四个状态

输入字母是ab 另外还有ε转移

那对这样一个状态转移图表示的NFA

它的状态转移表该怎么给呢

那我们之前第一列

依然是我们的状态

有q0

q0是初始状态

q1、q2

q2是终态

q3

它的输入字母ab

但是我们距这里有一个空串

我们把空串 也把它作为一列来表示

那我们就看我们每一个状态

对每一个输入字母

它输入之后转移的结果

q0它输入a转移到q1

它输入b的时候没转移

按说这个地方是一个空集

我们可以写成一个空集

但我们这里没写 就表示它是空集

q0它输入ε之后

那之前我们给DFA定义的时候

就是扩展的状态转移

认为它可以转到q0

但是我们这里强调的

是ε作为输入转到其它的状态的时候

那它这里就没有转移到它不同的状态

所以我们把这里也记为空集

q1输入a的时候没转移

输入b的时候转移到q2

那输入ε还是没转移

q2输入a的时候没转移

输入b的时候没转移

但是它输入ε的时候 它就可以转到q3

q3输入a的时候 没转移 是空集

输入b的时候 没转移 是空集

但是输入ε的时候 它就转移到状态q0

这个状态转移图对应的状态转移表

是这样表示的

当然有的同学就觉得

这一个空串作为一个单独输入

这样表示 好像是有点多余

我们可以用其它的形式把它代替

那就是我们下面要讲的ε闭包

任何一个状态q 它的ε闭包

是包含q的这么一个集合

它由状态q通过ε 路径能够到达的所有的状态

表示q的ε闭包

并把它记为EC（q）

当我们用严格的定义

就是归纳定义给出来的

给出一个NFA

任何一个状态q

它的ε闭包就是这样定义的

q设为自己的ε闭包

这个是归纳基础

另外假如p是q的ε闭包

而且p经过输入ε 它能够到达状态r

那r也在q的ε闭包里面

也就是说第二部分

这一部分是归纳假设

这个就是一个归纳推导

我们按这种方式

就给出了任何状态q的ε闭包

我们还可以给出一个集合的ε闭包

S是一个集合

它的ε闭包是这样定义的

是S这个集合里面

任何一个状态 它的ε闭包

把它并起来得到的集合

这是任何一个集合的ε闭包

有了ε闭包这个概念

我们下面可以求出任何一个状态ε闭包

比如刚才给的这个自动机

我们对状态q2它的ε闭包

首先它包含它自己q2

在q2能够ε

能够到达的状态有q3 有q0

所以q2的ε闭包就是q2、q3、q0

那看状态q3的ε闭包

它通过ε能够到达的状态是q0

在它自己这个状态

所以q3 ε闭包就是q3和q0

下面我们再看一个例子

这里是用自元素来表示的状态

有7个状态

我们看看这里面状态1它的ε闭包

首先当然是包含它自己

它通过ε转移状态1

还可以到达状态2

通过ε转移可以到达状态3

还可以到达状态6 状态7 状态5

那状态3通过ε转移

还可以到达状态4

也就是说状态1它的ε闭包

应该是1、2、4、5、6、7这些状态

那状态2的ε闭包

根据刚才我们看

它包含的状态2 状态3 状态6

状态7 状态5 状态4

那状态6的ε闭包

我看同学们就很容易得到

这样我们就给出了任何一个状态

它的ε闭包

有了ε闭包 对写状态转移表

就不需要把ε单独做一列

在后面我们做状态转移函数的扩展

我们要用到ε闭包

好 这一节的内容讲到这里

谢谢大家