当前课程知识点:软件理论基础 > 第三章 非确定有限自动机 > 3.5 等价性证明 > 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
-习题--作业
-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
-习题--作业
-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
-习题--作业
-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
-习题--作业
-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
-习题--作业
-期中考试