当前课程知识点：软件理论基础 > 第三章 非确定有限自动机 > 3.2 e转移 > Video
欢迎同学们来到《软件理论基础》的MOOC课堂
现在我们介绍
非确定有限自动机的第二部分
也就是ε转移
我们看看下面这一个状态转移图
输入字母是a
所不同的是在这一条路径上面
有一个输入字母是ε
上一次讲DFA的时候
介绍了扩展的状态转移函数
那里面也有一个ε转移
但是那里的ε转移只是在一个状态上面
它有一个自环
它不像这样从一个状态输入一个ε
转移到另外一个状态
这是在之前讲的DFA里面是没有过的
那我们看看这个自动机
它是怎么样运作的
从初始状态输入字母a 它是转移到q1
但是在q1这个地方 它有一个ε转移
那我们也可以认为在字母a后面
可以连接一个ε
如果在q1再输入ε的时候
它就到了q2
也就是说输入a
它就有两种或者多种选择
这跟我们之前讲的
非确定有限自动机就很类似了
我们给了输入字母串aa
从初始状态q0开始
输入a的时候 它到了q1
q1再输入a
后面它是一个ε
那我们没a的时候有ε
你就直接按ε来输入
也就是说在aa中间呢
我们可以看做插入了一个ε
因为ε它具有这种功能
也就是说任何字符
你左连接或者右连接一个ε
它跟原来这个字符是完全一样的
q1在输入ε时到q2
在q2再输入a的时候
这里有路径a 它到了q3
这个串输入完了
最后落在一个终态
那之前我们的定义
这个输入串在中间是接受的
那我们再看看
另外给一个输入串aa
从初始状态q0开始
输入a 到了q1
q1后面是跟了ε
那我们在ε直接转移到q2
q2读了a 这里有a
到q3
虽然这是一个终态
但是我们的串还没读完
再输入一个a
这个时候到了状态q4
串输入完了
但是落在一个非终态
那我们之前定义输入出来的
就是一个拒绝
这样字符串aa
就是被这个自动机是拒绝的
对这个自动机来说
它接受的语言只有aa
这跟我们上一节讲的NFA这个自动机
实际上是很类似的
这里面它接受的语言也是aa
它的选择也跟这个自动机很类似的
对这个自动机来说
它既可以用ε转移来表示
也可以用其它的路径来表示
我们再看看另外一个例子
这里是给的四个状态
我们输入的字母是ab
这里有两个ε转移
我们看这个自动机 它是怎么样运作的
我们的输入串ab
从初始状态q0导入a到q1
再输入b的时候 它就到了q2
这个串输入完了
最后落在一个终态
那之前我们定义
它输出的应该是接受
那我们再看看另外一个输入串abab
从初始状态输入a的时候 它到了q1
再输入b的时候 它到了q2
到q2这个串没读完 还需要a
但是后面是ε
直接跳到q3
q3也没有a 是个ε转移
我们再继续转移到q0
在q0这里有a
那我们再输入a 就转移到q1
在q1再输入b 就转移到q2
那我们这个串输入完了之后
落在一个终态q2
输出来的就是接受
那对这个自动机来说
这个自动机它接受的串应该是
ab，abab，ababab等等
我们可以把接受串
写成我们之前给出的
一个正闭包的形式
就是ab的正闭包
这就是这个自动机解释的语言
我们再看一个例子
这个例子里面它有三个状态
输入字母是01
它这里面有ε转移
在有的状态里面它有多个转移
有的状态里面它没有转移
所以这是一个明显的NFA
那对这个自动机来说 它接受的语言
同学们可以看一看
所以它接受的语言
只有从q0，q1，q0，q1之间再得到了
那它接受的语言
可以写成10的kleene闭包
或者是*闭包
我们看这个q2这个状态实际上
在这个自动机里面
它是没有任何作用的
它是个无用状态
我们对刚才的
自动机的输入串里面要做一些确认
第一个说明了虽然有ε转移
但是ε它是不出现在输入串里面的
另外这个自动机 它是非终态的
它接受的语言就是一个空集
而这个自动机是初态也是终态
它接受的语言是空串
所以这两个自动机 形式好像很类似
但是它们实质是不一样的
刚才介绍了ε转移
等会儿我们再给出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
-习题--作业
-期中考试
