当前课程知识点：软件理论基础 > 第二章 确定有限自动机 > 2.2 确定有限自动机的定义 > Video
欢迎同学们来到《软件理论基础》的MOOC课堂
我们继续介绍确定有限自动机
下面我们讲确定有限自动机的定义
在上讲里面我们给出了
确定有限自动机的概念
和一些实际的例子
通过这些例子
我们可以总结出
确定有限自动机它的几个基本要素
在这些例子里面我们可以看出
确定有限自动机 它有状态 有输入字母
有状态转移函数 还有初始状态 再有终态
我们可以根据这些要素
来给出确定有限自动机的模型
或者是确定有限自动机的形式化定义
一个确定有限自动机
它实际上是一个五元组
这个五元组包含有 有限状态构成的集合
输入字母构成的集合 状态转移函数
还有一个初态 再还有终态
状态集合里面 包含的是一个特殊的状态
初态q0
还有若干个终态构成的子集
在这个确定有限自动机里面
特别重要的就是状态转移函数δ
δ实际上是状态q和输入字母
到状态当中的一个映射
这个映射实际上
它是对于任给一个状态或一个输入字符
到另外一个状态的一个确定的映射
这个映射它只有一项
所以这是我们叫确定有限自动机
也简称为DFA
首先我们看这样的一个状态转移图
它的输入字母就是a、b
状态集合就是由q0到q5
这六个状态构成的集合
初始状态就是q0
它的终态实际上在这里面
就是q2和q4两个状态构成的集合
这里面最重要的就是状态转移函数δ
它是由状态转移函数来确定的
同时也可以通过状态转移图来确定
它们二者之间是一一对应的关系
我们通过状态转移图
可以给出状态转移函数
也可以通过状态转移函数
来给出状态转移图
状态转移图是q0输入a到q1
那它的状态转移函数
就是q0输入a 通过转移到q1
那么再看另外一个
q0输入b到q5
那状态转移函数就是q0输入b到q5
还有我们状态q2
这里表示的输入a或者输入b
都转移到状态q3
状态转移函数就是q2输入a
可以转移到q3
q2输入b也转移到q3
通过状态转移图或者状态转移函数
都能够确定我们的DFA
实际上还有另外一种方式
就是叫状态转移表
那通过这个状态转移图
我们怎么生成这样的状态转移表呢
我们就把这个表的第一列
就是我们这个自动机的所有的状态
这个状态里面打这么一个箭头的状态
是我们自动机里面的初态
你像q2、q4这里面就是这两个终态
那在这个状态转移表里面第一行
实际上就是我们的这个自动机的输入字母
你像a和b
那我们怎么生成这个表呢
像这个δ在q0
如果输入a它转移到q1
那我们q0输入a
在这个格子里面就填上q1
那q0输入b转到q5
q0输入b转到q5
我们再看q3
q3输入a它转移到q4
q3输入a转移到q4
那q3输入b转移到q5
q3输入b转入到q5
我们就可以把一个状态转移图
转成这个状态转移表
当然也可以把一个状态转移函数
写成一个状态转移表
我们再看另外一个例子
这是我们前面介绍的一个确定有限自动机
这个自动机它的状态转移函数
有这样描述的
这是它的状态集
这是输入字母集
这是状态转移函数
这是初始状态 这是终态
这个自动机
也可以用状态转移表来表示
这个表就是通过这个状态转移函数
我指状态转移图
就可以生成这样的一个状态转移表
那这个表的表示跟刚才是一样的
我们第一列是状态
第一行是输入字符
这里面对应关系通过状态转移图
或者状态转移函数来给出
从这个表里面我们可以看出
确定有限自动机
它是对一个状态给一个输入字符
必然要转移到一个状态
而且只有一个状态
所以我们这一个表
必须每一个都要把它填的满满的
而且只能填一个状态
这就是我们确定有限自动机的它的含义
这是我们讲的确定有限自动机的定义
特别是在这里面
我们的状态转移函数
是我们自动机的核心
我们这里给的一个状态
给一个输入字符
它到另外一个状态 它也有转移
我们之后还讨论一个状态 输入一个串
它是怎么做转移的
这是我们下一讲的讲的内容
这节内容讲到这里
谢谢大家
-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
-习题--作业
-期中考试
