当前课程知识点：软件理论基础 > 第三章 非确定有限自动机 > 3.1 非确定有限自动机的概念 > Video
欢迎同学们来到《软件理论基础》的MOOC课堂
我是清华大学的教师 罗贵明
今天我们要介绍的是非确定有限自动机
内容包括非确定有限自动机的概念 ε转移
非确定有限自动机的定义
扩展转移函数 等价性证明
最后介绍文本搜索
什么是非确定有限自动机
在上一讲里面我们介绍了确定有限自动机
确定有限自动机最大的特点
就是它的状态转移函数
对每一个状态
或每一个输入字母
它都有一个转移
而且只有一个转移
那我们看看下面这个例子
这是一个自动机的状态转移图
输入字母是a
在状态q0
我们输入字母a的时候
它有两个转移
这跟我们之前介绍的自动机是不一样的
再看看在状态q3和q4输入字母a
它们都没有转移
这就跟我们之前讲的DFA
明显是不一样的
这个自动机它是怎么运作的
我们对输入串aa
首先从初始状态q0
等于a的时候
它有两种选择
我们首先选择第一条路径
它转移到q1
再输入a的时候
它转移到q2
这个输入串都完了 落在一个终态
按照我们上一次介绍的DFA解释的概念
那这个串被这个自动机是接受的
也就是说在这条路径上面
这个串是被接受的
当然对于这一个串的它的输入
它有两种选择
那我们再看看在另外一条路径
在初始状态导入a的时候
它就转移到状态q4
再导入a的时候 发现这没有转移
在这个自动机里面 它就停机了
就把它输出的是拒绝
所以对这一个输入串
这个状态转移图
它就有两种结论了
在这条路径上面是接受的
在这条路径上是拒绝的
那这样跟我们之前
介绍的DFA的接受是完全不一样的
那我们定义像这样的自动机
它的接受是怎么样给出来的
一个字符串在一条路径上面 它被接受
是这个字符串在这个路径上面
是输入完了
而且最后处于在自动机的一个终态
那一个串被自动机接受
是这个NFA 它至少存在一条路径
接受了这个字符串
我们就说这个字符串
被这个NFA是接受的
那我们再看看前面的自动机
输入串aa
被这条路径里面 它是接受的
但它被这一条路径里面 它是拒绝的
那我们定义来说 这个输入串aa
就被这个自动机是接受的
我们再看看另外的一个输入串
这个输入串是aaa
同样我们从初始状态q0开始
导入a的时候 它有两种选择
我们首先走这条路径
再输入一个字符a 它转移到q2
q2虽然是终态
但是这个字符串还没读完
那我们再输入a
这个时候 它转移到q3
输入串读完了
它最后落在一个非终态q3
那输出的是拒绝
那我们再看看它走另外一条途径q0
从q0开始 读a的时候 它转移到q4
q4这里再没有其它的转移了
我再输入a的时候 它就没路径
这个时候它就停机了
输出的是拒绝
也就是说这个输入串 尽管有多种选择
但是在这一条选择里面 它是拒绝的
在另外一条选择里面 还是拒绝的
首先我们定义
被一条路径拒绝
被一条路径拒绝 是这个字符串
它输入完了
但是状态不在终态上面
或者这个字符串在这条路径上面
是无法输入完的
这两种情况都叫做这个输入串
在这条路径上面是被拒绝的
那一个输入串被自动机NFA拒绝
是指的没有一条路径
来接受这个字符串w
就叫做这个w被NFA拒绝
我们把NFA里面 被它接受的串
放到一个集合里面
就叫做这个NFA的语言
这个定义倒是跟我们之前讲的
DFA的语言是很类似的
那下面我们看看
被刚才的这个自动机
输入串aaa
在这条路径里面 是被拒绝的
在这一条路径里面 也是被拒绝的
所以没有一条路径
来接受这个字符串aaa
这个aaa这个字符串
被NFA所有路径是拒绝的
因此 它是不被NFA接受的
那这个自动机
它接受的语言
只有aaa这一个串
好 这节内容讲到这里
谢谢大家
-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
-习题--作业
-期中考试
