当前课程知识点：软件理论基础 > 第三章 非确定有限自动机 > 3.4 扩展转移函数 > Video
欢迎同学们来到《软件理论基础》的MOOC课堂
现在我们讲述本章的第四节
扩展状态转移函数
NFA的状态转移函数
是状态输入字母
到状态的幂集合当中的一个映射
那现在我们要对
这样一个状态转移函数进行扩展
我们的扩展与前面的DFA的扩展
既类似也有不同
原来是状态转移函数
对每一个输入字母
或者是空串进行转移
状态转移对输入串进行扩展
这个扩展跟我们前面的
DFA的扩展是很类似的
另外我们还有一个扩展
状态转移
它转移的不是一个单独的状态
而是这个状态的ε闭包
这跟我们前面讲的DFA就有所不同
这7个状态
这是我们前面介绍的一个NFA
对状态1输入字母b
因为这是单独一个字符
我们的扩展就应该是扩展到ε闭包
我们从状态1输入字母b
扩展的转移就得到
这3、4、5、6、7 这几个状态
另外
从状态1输入字符串bb
是它转移到bb的ε闭包
最后得到的是转移到状态4
状态1输入ba
它得到的ε闭包就有3、4、5、6、7
我们前面给的是一个描述性定义
现在我们给出
状态转移函数的形式化定义
对状态qi
通过qi有一条路径到qj
qj有个ε转移到qjk
qjk就应该输入qi通过w这个串转移的
它的扩展转移
那这个串我们可以把它分解为
这k个字符逐个证明的转移
这样我们得到它的状态转移的扩展
我们有了状态转移的扩展
那我们就可以给出
NFA语言的形式化定义
如果在之前我们介绍NFA语言的时候
我们是这样给出来的
就是NFA 如果是有一条路径接受这个串
那我们就说NFA接受这个串
把它所有的串放在一个集合里面
就是构成这个NFA的语言
这是我们用自然语言描述的
但是我们的计算机是不理解
你这种描述形式的
就如同DFA的描述一样
我们要采用形式化描述
NFA的形式描述
就把刚才的我们自然语言
怎么转化为计算机
能理解的这种语言呢
这就是我们利用之前讲的
把状态转移函数进行扩展
我们就可以定义NFA它的语言的形式化形式
假设这是一个NFA
这个w经过扩展的状态转移
这转移的集合
它跟接受状态它的叫不等空
我们把这样的串放在一个集合里面
这个集合就是我们的NFA的语言
我们用这样一种形式就非常简易的
把NFA的语言给出来了
而这种给出形式计算机是能理解的
前面给出的形式化定义
我们可以用这种描述
给了NFAM
它接受的语言
这语言包含若干串
这个串具有这种形式
这个串它是有初始状态
经过扩展的状态转移
转移到这里面来
这个状态集合里面
至少有一个状态是终态
这个串就是这个语言里面
也就是我们下面用这个图的形式
非常形象的描述
我们给出的语言的这个形式
从初始状态开始
它应该经过w这个路径
就可以转移到很多个状态
你比如说它可以转移到q1
它可以转移到qk
它可以转移到qj等等
在这个转移过程当中
如果有一个状态qk是终态里面的一个状态
那我们就把这个w
就放在这个语言里面
就得到这个NFA的语言
下面我们看这个例子
这是前面描述了一个NFA状态转移图
它的终态是3和7
这样一个串
我们前面讲过的
状态1输入b
它转移的这个ε闭包
就得到3、4、5、6、7
这里面大家可以看出
3实际上7也是终态
只要有一个终态就OK了
那这个b就应该在NFA这个语言里面
我们下面再看另外一个串
从初始状态输入串baa
通过扩展的状态转移
它就转移到3、4、5、6、7
这里面3和7都是终态
因此这个串baa也在这个语言里面
那我们再看另外一个输入串bb
从初始状态输入bb
经过扩展的状态转移 就转移到4
4 我们看它不是接受状态
因此 这个bb就不在这个NFA的语言里面
这个语言实际上
我们可以写成为
b连接后面的a的kleene闭包
也就是*闭包
这就得到这个NFA的语言
在前面我们讲了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
-习题--作业
-期中考试
