当前课程知识点:软件理论基础 >  第三章 非确定有限自动机 >  3.5 等价性证明 >  Video

返回《软件理论基础》慕课在线视频课程列表

Video在线视频

Video

下一节:Video

返回《软件理论基础》慕课在线视频列表

Video课程教案、知识点、字幕

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

现在我们讲这一章里面的第五个部分

就是等价性证明

首先我们看这个例子

这是一个自动机 它是一个NFA

它接受的语言

我们看前面已经讲过

这是另外一个自动机

这个自动机是DFA

这两个不同的自动机

但是它们接受的语言是一样的

如果有自动机M1和自动机M2

它们两个的语言是相同的话

那我们就称这两个自动机是等价的

就像刚才这个自动机 它接受的语言

和这个自动机 它接受的语言

都是10* 语言是相同的

因此 这两个自动机是等价的

那大家要注意

这是一个NFA

这是一个DFA

DFA我们前面讲了

它接受的语言是正则语言

而NFA我们只定义它的语言

那它的语言刚好跟他们是相等的

这是偶然的吗

这就是我们下面要讲的

NFA接受的语言和正则语言

正则语言也就是有DFA接受的语言

它们之间是相等的

也就是说这个语言的集合

和这个语言的集合是完全相同的

那我们就知道NFA和DFA

它们表现能力是相同的

那我们要证明这个两个集合相等

这都是集合

那实际上就要证明两方面

正则语言包含在

NFA接受的语言里面

这是我们需要证明第一个部分

第二个部分是NFA接受的语言

包含在正则语言里面

第一个部分的证明

实际上是非常显然的

也就是任何一个DFA

实际上它是NFA的一个特殊情况

所以DFA接受的语言

一定是NFA接受的语言

比如说正则语言

包含在NFA这个语言里面

那反过来我们要证明

NFA接受的语言也包含在正则语言里面

那我们要证明这一点

实际上就是跟一个NFA

你要证明有一个DFA

来接受跟NFA相同的语言

那这就是一个构造过程了

我们下面看这个例子

这是三个状态

它刻划的是一个NFA

通过这个NFA

能不能找到一个DFA

或者构造一个DFA

它接受的语言跟它相同

那我们怎么去构造呢

下面我们通过这个NFA

想办法去找DFA它的状态

它的输入字母嘛语言相同

应该输入字母是一样的

它的转移关系怎么给

初始状态怎么给

还有终态怎么给

这个都是我们要构造DFA里面

必须要想到的

那下面我们通过这个NFA要构造DFA

第一步我们就要构造这个DFA的初态

因为NFA的初态这一个

我构造DFA的初态就很简单

我就采用这个NFA的初态q0

它的信息来构造DFA

我们用这么一个符号来表示这个初态

这个q0是NFA的初态

我们用一个括号括起来

这里表示是DFA的它的初态

它只是包含了NFA的信息

那接下来对这个状态

要对它这个输入字母a和b

都要有转移

这才是我们的DFA

那到这个状态输入a

该转移到哪个状态呢

那这个时候我们因为要讨论

你构造的这个DFA跟NFA它是等价的

接受的语言相同的

那看这个状态输入a转移到哪个状态

那我们回头就看

你这个原来NFA里面

q0输入a我们看它转移到哪个状态

我们看这是转移到q1

但这还不够

我们要看转移到q1它的ε闭包

那这里q1的ε闭包呢 有q1q2

所以在NFA里面q0输入a

它的转移的ε闭包就是q1q2

这样我们在DFA里面构造的时候

这个DFA的状态 它输入a

就应该转移到这个状态

这个状态虽然写的q1q2

它只是包含着NFA q1状态和q2状态的信息

但是在DFA里面

我们用这个方法括起来

只是一个状态的记号

它表示一个状态

这个状态就是有q1和q2

包含信息的一个状态

这一个在DFA里面

它输入a 就转移到这个状态

那这个状态还要输入b

它必须要有一个转移

我们再看这个

这个状态输入b 该转移到哪呢

那我们还是回到NFA里面看

NFA里面它q0输入b的时候 它没有转移

那没有转移 我们在NFA里面

是用一个空集表示的

所以我们在这里

就用一个新的状态 就是空状态

空集表示状态

就是这个状态输入b就转移到这儿来

那空集表示的状态是在NFA里面没有的

那这个转移很简单

它就是用一个自环就可以了

那接下来我们就要考虑

这个状态q1 q2描述的这个状态

这个状态也分别对a和b必须要转移

这个状态输入a的时候

它会转移到哪

我们看在NFA里面

q1输入a的时候 它转移到哪

q2输入a的时候 它转移到哪

那我们首先看看q1在NFA里面

它输入a它转移到q1

那我们强调的不是转移到这一个状态

我们还考虑它的ε闭包

也就是说q1输入a的时候

它转移ε闭包是q1q2这两个状态

q2输入a 这里没有转移

我们把两种情况把它并在一块

那我们就说q1q2在NFA里面

输入a的时候

它转移的所有的状态集合

实际上还是q1q2

那这里实际上就是

这个状态输入a的时候是一个自环

这个状态输入a已经有了

那我们再看这个状态再输入b的时候

看它转移到哪

那我们还是回到这个NFA里面

看q1输入b的时候转移到哪

q2输入b的时候转移到哪

在q1里面输入b的时候

我们看它是没有转移的

q2输入b的时候 它转移到q0

因此 我们把这两个状态

它输入b的时候 它的转移状态进行并集

实际上它就是转移到q0

也是在我们这个DFA里面

报q0信息指这个状态

从这一个状态输入b的时候

它转移到这儿来

这样 我们这个DFA的构造

就基本上构造完了

它对每一个状态

对每一个输入字母都有一个转移

但我们还没有终态

那我们的终态 还是回到我们的NFA里面

NFA里面终态是q1

那我们在DFA里面呢

你看这个状态里面

它包含有NFA的终态q1

其它的没有

所以只要是包含有NFA的

终态的信息的话

这样的状态

我们就把它定义为DFA的终态

那这个终态已经构造出来了

我们这个构造的这个DFA

完全是按照NFA的

它的信息来构造的

所以它们接受的语言应该是相同的

这是通过这个例子

我们给出了从NFA到DFA的构造

那对一般的情形

可以把刚才的那个算法

总结出下面的一个转换算法

给定了NFA五元组

我们要把它转化为

跟它等价的一个DFAM′

我们要构造这样的M′

第一步 DFA的状态怎么写

我们知道NFA的状态是Q

Q是q0、q1、q2等等 它是有限状态

那我们在选取DFA的状态M′的时候

我们就把这样的集合

也就是它的幂集合

这就相当于φ空集

q0一个状态

q1、q2

q1、q3

q1、q2、q3

所有的DFA里面的

状态的集合就有很多个

相当于NFA状态的它的幂集合

那状态的个数就很多了

就是首先我们把DFA的状态集

我们已经确定了

初态我们的选取

就是按刚才的例子一样

因为NFA的初态是q0

我们选取的DFA的初态

是只是包含这一个状态的信息的

就像我们刚才的例子里面

我们选取的初态对这样的一个NFA

它的初态是q0

我们DFA的初态就选取的是这样的

初态得到之后

算法的第二步就是确定对DFA里面

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

我们必须要有一个转移

就像DFA里面

我们现在有这一个状态

qi、qj等等 qm

这个qi、qj、等等 qm就是NFA里面的状态

我们把它括起来这里就表示

这含有NFA这些状态的信息

但是它是DFA里面的一个状态

那这个状态要对每一个输入字母

它必须要转移

这个转移在DFA里面

它会转移到哪个状态呢

那我们现在又回到NFA里面看

NFA里面我们看qi输入a的时候

它的扩展的状态转移

我们把它所有的状态给出来

它qj输入a的时候

我们也把它的扩展的状态转移

有些是它的ε闭包里面都放下的状态

给出来等等

把所有的

包括这里面的所有的状态输入a

它ε闭包转移都给出来

我们通过刚才的NFA的转移

转移到它的状态的集合是这样的集合

那我们在DFA里面

就给出这样的一个转移

就是在这个状态qi、qj、qm

这是DFA里面的状态

那输入a的时候

它的转移就是转移到

包含NFA这些信息的一个状态

这是我们对每一个状态

每一个输入字母 它的转移

它的结构是这样的

上个例子里面

这是NFA

我们的初态是在NFA里面 初态q0输入a

它的ε闭包得到的是q1、q2

那在转化的DFA里面

它的初态q0输入a 它就转移了

应该转移到包含NFA状态信息q1、q2的

这样确定的一个状态里面

这是我们按算法的

刚才的第二步来构造的

我们重复这个步骤2的话

直到没有新的状态转移

也就是像我们刚才这个例子里面

我们这里给了NFA

我们重复我们刚才的步骤2

就得到DFA这个状态转移

这个状态转移它对每一个状态

对每一个输入字母都有一个转移

而且只有一个转移

这就是一个DFA

但是它的终态我们现在还没定

那终态呢

如果在DFA里面有这个状态

qi、qj、qm

状态里面

只要是有一个状态是NFA终态的话

就称为DFA里面的终态

就像我们这个例子里面

q1是NFA里面的终态

那在DFA里面

就指这一个状态

包含有NFA终态的q1的信息

其它都没有

所以这个状态就是DFA它的终态

把NFA转化为

跟它等价的这个DFA

这个算法我们是按这样给出来的

从NFA构造出DFA

但是它们是不是这两个自动机

给出的语言是相同的

也就是说你这构造的这两个自动机

是不是一样等价的呢

这下面我们必须要从理论上要进行验证

下面得到结论

给定了NFA

我们通过上面的算法得到DFA

这样DFA跟NFA一定是等价的

也就是它们的语言是相同的

要证明这一点就

因为语言是集合

必须要证明这个NFA的语言

包含在DFA的语言里面

反过来也证明这个DFA的语言

包含在NFA里面去

我们先证明第一个包含关系

也就是NFA的语言

包含在DFA的语言里面

也就是要证明

对NFA里面每一个字符串

这个字符串它只要输入NFA的话

就从q0到qf就有一条路径来

就是w这个路径到达终态

这个字符串可以分解为σ1、σ2、σk

也就是在NFA里面从初态q0开始

分别经过σ1、σ2 又到σk 到终态qf

那我们要证明经过这个字符串

在我们构造的DFAM当中

就有这样一条路径

这个路径的状态分别是q0

这个括号一直到qf这样

这里面上面标的输入字符串

跟这是一样的

从这个初态到DFA的终态这个路径

我们就可以肯定

这个w是输入DFA里面的语言了

那要证明这一点

我们用归纳法证明

归纳法证明

那我们就不能够一直是初态到终态

我们讨论跟一般的字符串

你像这个字符串是a1、a2、an

它是从NFA的初态

从初态q0分别输入a1转到qi

输入a2转移到q1等等等等

到qa2输入an转到qm

那一定成立这样的一条路径在DFA里面

这个路径上面的状态是

含有q0信息的一个状态

含有qi信息的一个状态

还有qj信息的一个状态

还有ql信息的状态

还有qm信息的状态

这个状态它分别是由a1、a2、an

转移到这儿来的

用归纳法我们要证明这个成立

我们是用串的长度做归纳

当串的长度为1的时候

也就是v等于a1

我们证明刚才的那个结论是成立的

也就是从初态q0经过a1转移到qi

那在DFA里面一定有这种转移

从DFA初态输入a1 转移到另外一个状态

这是包含有qi信息的一个状态

这是我们在算法里面

我们就是这样规定的

所以这个是自然成立

那假设当V的长度大于等于1

小等于k

也就是V等于a1、a2、ak的时候

我们的结论是成立的

也就是有一个长度为K的这一个串

从q0到qm在NFA里面有这个转移

那在DFA里面具有这样一个状态转移

初态是q0

最后一个状态

是包含qm信息的一个状态

中间都是分别包含qi的信息

包含qj的信息

包含qc的信息

而每一条路径上面

这个a1跟这是一样的

a2跟这是一样的

ak跟这是一样的

我们假设长度为k的时候

这个是成立的

当V的长度为k+1的时候

也就是V可以写成为

长度为k的这一个串

我们用V′表示

这后面连接一个a的k+1

也就是表示V′ak+1

这个字符串里面可以表示成为

M是长度这是为V

而前面这一部分就是我们的V′

在DFA里面

前面这一部分就是V′

因为我们的归纳假设是这样给的

这个V′是长度为k

它有这样一个转移

在DFA里面也应该有这个转移的

这个是在归纳假设保证了

那从qc到qm 假如输入ak+1

能够转移到qm的话

那在我们的算法里面就包含qc的这一个

状态信息的DFA状态

输入ak+1就一定能够转移到

包含qm信息的

这一个DFA的状态里面

这是我们的算法规定的

所以一定有这个状态

输入ak+1转移到这个状态

刚才的从q0到qm

输入这个串V的时候

也一定能够从q0这个状态

转移到包含qm信息的这个状态

这就说明对长度V等于k+1的时候

这个结论也是成立的

那这样 我们就证明了

对任何一个串w等于σ1、σ2、σk

它是属于NFA里面的串话

那也就是这一个串w

也输入DFA里面接受的语言的串

这样我们就证明了NFA里面这个语言

它就是包含在DFA里面

那我们也可以类似的方法

来证明这个DFA的语言

它也包含在NFA里面

证明了这两点之后

我们就可以下结论

我们的算法的确能够保证

我们构造的自动机

跟NFA得到的自动机是等价的

也就是它们的语言是相同的

这个定理 我们要做一点说明

这个定理证明了

任何一个NFA

一定有一个DFA跟它等价

或者说DFA描述的语言

跟NFA表示的语言的集合是相同的

NFA接受的语言

因为我们知道DFA接受的语言是正则语言

那NFA接受的语言也是正则语言

这是我们第一点要说明的

第二点虽然NFA与DFA它们是等价的

但是它们的复杂度可是不一样的

我们从NFA转DFA可以看出

NFA里面它的状态可能是n个状态

而DFA里面的状态

是NFA里面的状态的幂集合

所以它转的状态的个数

就可能要多很多了

那变迁也随之要多很多

也就是说它们的复杂度

可能是不一样的

好 这一节就讲到这里

谢谢大家

软件理论基础课程列表:

第一章 基础知识

-1.1 概要

--第一节

-1.2 数学基础

--Video

-1.3 图

--Video

-1.4 证明方法

--Video

-1.5 语言基础

--Video

-1.6 语言运算

--Video

-习题--作业

第二章 确定有限自动机

-2.1 确定有限自动机的概念

--Video

-2.2 确定有限自动机的定义

--Video

-2.3 扩展转移函数

--Video

-2.4 正则语言

--Video

-2.5 DFA构造

--Video

-习题--作业

第三章 非确定有限自动机

-3.1 非确定有限自动机的概念

--Video

-3.2 e转移

--Video

-3.3 非确定有限自动机的定义

--Video

-3.4 扩展转移函数

--Video

-3.5 等价性证明

--Video

-3.6 文本搜索

--Video

-习题--作业

第四章 正则表示

-4.1 单一终结状态的NFA

--Video

-4.2 正则语言的运算性质

--Video

-4.3 正则表示和语言

--Video

-4.4 正则表示和正则语言

--Video

-4.5 正则语言的同态

--Video

-4.6 正则表示的代数定律

--Video

-习题--作业

第五章 正则文法和正则语言

-5.1 文法

--Video

-5.2 线性文法

--Video

-5.3 正则文法与正则语言

--Video

-5.4 自动机的积

--Video

-习题--作业

第六章 正则语言的性质与DFA优化

-6.1 基本问题

--Video

-6.2 泵引理

--Video

-6.3 非正则语言的判定 1

--Video

-6.4 非正则语言的判定 2

--Video

-6.5 DFA的优化 1

--Video

-6.6 DFA的优化 2

--Video

-习题--作业

第七章 上下文无关文法和推导

-7.1 上下文无关文法

--Video

-7.2 规约和推导

--Video

-7.3 语法分析树

--Video

-7.4 规约、推导和语法分析树之间的关系

--Video

-7.5 上下文无关语言

--Video

-习题--作业

第八章 CFG的应用与文法的二义性

-8.1 CFG的应用

--Video

-8.2 CFG的转化

--Video

-8.3 文法二义性

--Video

-8.4 二义性的消除方法

--Video

-8.5 CFG的构造方法

--Video

-8.6 CFG的构造实例

--Video

-第八章 CFG的应用与文法的二义性--习题

第九章 下推自动机

-9.1 PDA介绍

--Video

-9.2 PDA的定义

--Video

-9.3 PDA的即时描述

--Video

-9.4 PDA的语言

--Video

-9.5 PDA与CFG的关系

--Video

-习题--作业

第十章 下推自动机与CFG化简规范

-10.1 确定下推自动机

--Video

-10.2 DPDA与其他语言的关系

--Video

-10.3 终态型DPDA和空栈型DPDA

--Video

-10.4 消除无用符号

--Video

-10.5 消除e产生式

--Video

-10.6 消除单一产生式

--Video

-10.7 CFG的化简与Chomsky范式

--Video

-习题--作业

第十一章 上下文无关语言的性质

-11.1 CFL的必要条件

--Video

-11.2 CFL的Pumping引理

--Video

-11.3 CFL的闭运算性质

--Video

-11.4 CFL的同态性质

--Video

-11.5 CFL的交运算

--Video

-11.6 CFL的判定性质

--Video

-习题--作业

第十二章 Turing机

-12.1 图灵机的介绍

--Video

-12.2 图灵机的定义

--Video

-12.3 图灵机的即时描述

--Video

-12.4 图灵机的计算

--Video

-12.5 图灵机的编程技术

--Video

-习题--作业

第十三章 图灵机的扩展

-13.1 Turing理论

--Video

-13.2 图灵机带的扩展

--Video

-13.3 图灵机移动的扩展

--Video

-13.4 受限图灵机

--Video

-13.5 图灵机与其他自动机

--Video

-习题--作业

第十四章 不可判定问题

-14.1 图灵机编码

--Video

-14.2 对角线语言与通用语言

--Video

-14.3 图灵机语言的性质

--Video

-14.4 判定问题和语言

--Video

-14.5 计算复杂性问题

--Video

-第十四章 不可判定问题--习题

第十五章 自动机及应用

-15.1 时间自动机

--Video

-15.2 Buchi自动机

--Video

-15.3 软件形式化验证

--Video

-15.4 模型检测方法

--Video

-15.5 M3C模型检测系统

--Video

-习题--作业

期中考试

-期中考试

Video笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。