Video在线视频

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

现在继续介绍DFA优化的最后一个部分

就是最优的DFA

在上一讲里面我们介绍了

DFA状态集上面的一个等价关系r

以及这个等价关系r

它的实现的算法 填表法

那我们根据这样的等价关系

以及这样的算法

怎么对DFA做优化呢

那下面我们介绍这个优化的步骤

我们就这样

首先删除这个DFA当中

从初态不可到达的所有的状态

当然这些状态 大家看

肯定是（01：11）的

因为它绝对不会产生语言的

这样我们得到了一个新的DFA

都是从初态可以到达的

假设这个DFA就是a

第二步 我们就用刚才定义的填表算法

找出这个状态集当中

所有的等价的状态偶对

就是根据填表法

第三步 我们根据这样找出的第二步

找出的所有的等价的状态偶对

就得到了它那些等价类

也就是状态集合的一个划分

这个划分就是我们所需要的

对每一个等价类或者每一个块

我们看作是一个状态

那这样在一个块当中的所有的状态

它是等价的

不同块当中的状态它是不等价的

那么等价的用前面介绍的方法

就是用这个记号来表示

它的等价类或者块

那根据这样我们就可以构造一个

跟DFA这个A等价的

一个新的自动机B

这个B的状态级用QB表示

这个QB就是

我们所有的等价类构成的集合

也就是一种∑级

δB也就是状态转移

状态转移我们定义了按这种方法

来定义状态转移

q0也就是初始状态等价类

FB是我们接受状态构成的等价类

那这样我们就把原来的这个DFA

就得到新的一个自动机B

这个新的自动机状态级是QB

QB是由所有等价类构成的

那它的状态个数的话

那一般来说它比原来的状态q应该少

我们首先看一个例子

这个例子

就是我们刚才介绍的那个自动机

有七个状态

刚才用填表法得到了等价的偶对有1、2

和6、7

也就是对7个状态进行划分

就得到的结果是这样5个类

我们按5个类构造了新的自动机

这个自动机跟这个自动机它的状态要少

但是它们的语言完全是相同的

大家可以验证

这就是我们利用填表法

对自动机状态做的优化

那利用填表法我们可以对DFA做优化

下面我们有个问题

你这里填表法是对原来的DFA做了优化

得到了自动机

这个自动机的状态Qm

是不是状态数最少的那种自动机

也就是说是不是还存在一个另外一个DFA

这个DFA它跟你的A是等价的

但是状态数比你这个Qm还少

如果说还有这样的自动机的话

那你就说你这个优化

还没达到最优的这种程度

下面我们证明了这种是不可能的

假设存在一个DFA

就是我们刚才说的假设这个DFA是n

它的状态是qn

这个DFA它的语言

跟原来的那个A 或者跟M

它是相同的

但是它的状态数比M要少

假设有这样的自动机

我们说会有什么结果

当然我们为了证明这个不可能

我们首先在这里做一些准备

首先我们假定M和N

它们之间没有重名的状态

这个状态命名嘛是你自己给定的

这跟语言没什么关系

另外 我们假设M和N每个状态

都是从初态可达的

我们首先做这类处理之后

下面我们构造一个叫并自动机M并 N

那个并自动机

实际上是状态级 它们之间并

还有状态转移它们之间并

这个我们打引号的实际上

就是在各个不同的自动机

它使用不同转移

初始状态 你要么写Qn的初始状态

要么写Qm初始状态

那么终态要把它们并起来

实际上这个并自动机

我们在上一讲里面讲语言的等价时候

我们已经介绍过这个并自动机

那我们对M和N进行刚才的这个并之后

我们就可以得出这个结论

首先是M和N的初态是不可分的

为什么 大家想一想

因为我们在那个填表法里面

我们定义了那个关系R

关系R是要么是同时到达终态

要么是它们都不达到终态

M和N它们两个语言是相同的

语言相同那就是对任何的串

要么从初态它们都能到终态

要么都到达不了终态

所以我们得出M和N的初态是不可分的

那接下来我们说假如p和q是不可区分的

那它们的后继状态也是不可区分的

这个根据我们填表法的归纳

我们马上可以得到这个结论

结论A和B

我们就推出了第三个结论

就是M的任意的一个状态

它就与N它当中一个状态是不可区分的

为什么 大家可以想一想

因为M的状态

我们假定是跟N的状态要多

那我们就得出M当中至少有两个状态

这个N当中一个状态是不可区分的

那根据不可区分的

它们具有传递性 就得出了M当中

至少有两个状态它是不可区分的

那这得出什么

因为M是填表法 它构造出来的

这不就矛盾了

这个矛盾就说明你刚才假定的

另外的一个DFAN状态数比M还少的

这是不存在的

所以我们证明了用填表法得到的这个DFA

他是一个最优的DFA

这就是我们得到了这个结论

那刚才我们举了一个例子

把七个状态通过优化

我们优化了有两个状态

只得了它五个等价类

可能有的同学对我们刚才填表法

就说你七个状态只优化了两个

好像这个力度不是很大

下面我们介绍几个例子

首先看这个例子

这是这样的语言 它的输入字母是0和1

0、1当中的奇偶性是相同的

也就是说0它的个数是奇数的话

1的个数是奇数

0的个数是偶数的话

1的个数是偶数

这样的话是被接受的

这个语言我们之前已经讲过

它的自动机是由四个状态构成的

那这个自动机我们用填表法

就可以容易的对它进行优化

这个优化就得到了

这个自动机实际上是两个状态就可以了

这是四个状态优化成两个

这说明这个优化的力度达到了50%

下面我们再介绍一个比这个例子

更复杂的一个例子

这个例子实际上是在之前第二章

我们已经讲过的例子

这个给了一个DFA是这样的

它的语言是输入字母是0、1

W当中它的长度

它不超过3的任意子串

最多只包含一个1

我们当时画这个自动机的时候

我们画的费了很大劲

实际上得到的自动机是这样的

它实际上有16个状态 有30多个变迁

像这样的自动机 肯定有融入状态

我们变迁怎么做优化

我们就按刚才的填表法

这个自动机把它的状态列出来

这个状态就得到了

它所有的状态得到是这样的

那我们填表法就得到

它们可区分的打XX的

没可区分的 你看都是没打XX的

那对这样的填表法

得到的最后的结果是什么呢

也是对这个自动机我们最后做优化

跟它等价的自动机就是这样的自动机

再看这个自动机只有四个状态

那比刚才这自动机它的状态数

你看减少了多少

从这个例子可以看出

我们填表法在使用的时候

在有些DFA里面是非常有效的

今天我们介绍了DFA的一些优化

定义了DFA状态上面的一个等价关系

以及实现这个等价关系的算法 填表法

而且我们证明了用这种方法

能够对DFA达到它的最优的程度

好 我们这节内容介绍完毕

谢谢大家