当前课程知识点:软件理论基础 > 第二章 确定有限自动机 > 2.3 扩展转移函数 > Video
欢迎同学们来到《软件理论基础》的MOOC课堂
今天我们继续介绍确定有限自动机
在上一讲中我们介绍了
确定有限自动机的定义
它是一个五元组
这里面最重要的是状态转移函数
状态转移函数它是给了一个状态
给了一个输入字符
它会转移到另外一个状态
这就是我们要把我们的自动机状态转移
进行扩展
在原来的状态转移图里面
这个自动机它是一个状态
对一个输入字母有一个转移
而现在给了一个状态 给了一个输入串
它到另外一个状态的一个转移
那这种转移是怎么转移的呢
我们下面看一看
下面给了状态q0和输入串ab
在这个自动机里面
我们看是怎么转移的
从q0的输入串
我们是依次从a和b来做转移
在q0的a它就转移到q1 那还没有完
在读b的时候 它就会转移到q2
这样我们就得到从q0输入ab
它就转移到q2
所以我们把这个扩展的状态转移
跟原来进行一个对比的话
这里就有一个* 就是δ*
δ*表示扩展的状态转移
下面我们再看从q0我们给了aa这个串
那我们还是在这个状态转移图里面来看
从q0依次输入a 再输入a 它落在状态q5
那如果是我们的输入串是abba在q0
那从q0依次输入abba
最后落在状态q4
所以它转移的结果是q4
对扩展的状态转移
定义它是在q这个状态输入一个串w
它转移到q1′
就是从q到q1′应该存在一个
这个串为w的一个路径
把它转移到q1′
这个w可以把它分解为每一个输入字符
那从确定有限自动机里面
从q开始它依次在σ1、σ2、σ3
一直到σK 最后转移到q1′
这就是我们给出的
从一个状态输入一个串
到另外一个状态的转移
前面是给的扩展状态转移的
一个描述性的一个表示
我下面我们要给出扩展状态转移的
递归的形式定义
首先我们说对任何一个状态
如果是空串的时候 它会转移它自身
这个我们把它作为这个定义的基础
如果在状态q输入一个串wσ
也就是一个串w后面连接另外一个字符σ
那我们定义采用关拉的形式来定义
因为前面有一个串w
那我们就要从q开始输入w
从串的长度来说 它要比wσ就少一个
那这个扩展转移 它会转移到一个状态
那从这个一个状态 再输入一个字符σ
再用标准的状态转移
它会转移到新的一个状态
这里就是一个归纳的形式
从图里面看
如果是假定从q开始 它会转移到状态q1
这是假定它有这么一个转移的话
那串的长度再增加一个σ的时候
那它就会转移到q1′
而这个转移就是我们标准的状态转移
从这里看
我们的这个扩展的状态转移
可以分成这样的几个步骤
首先从归纳假设q输入w
在扩展状态转移δ* 会转移到q1
而q1输入σ
经过标准的状态转移 会转移到q1′
那我们通过这样的代换
原来的q要输入wσ的时候
我们就会把这个转移
它是经过w转移 转移到q1 再输入σ
然后通过再一代换 这个δ*q是wσ
它就会转移到q1′
那最后我们就可以得到δ*在状态q是wσ
它最后会转移到这个递归的形式
这就是我们进行递归的定义
扩展的状态转移
下面我们看
怎样通过递归定义
对这个状态转移进行计算
首先我们说在q0输入ab
扩展的状态δ*
那我们从图里面看
q0输入ab
这里可以看出它是转移到q2
但是我们递归定义是这个串ab
可以分解为w和σ
我们的σ就是b
w就是a
所以我们归纳的这一部分
就是δq0到a的这个转移
然后是标准的状态转移
这个状态输入b
那这一步我们还要通过递归定义
a这个串 可以分解为一个空串
后面连接一个输入字符a
所以我们把这一个
通过递归定义 又可以写成为q0输入空串
然后转移的状态
最后输入a 进行标准状态转移
之后我们用归纳基础
这一个就是转移到q0
所以这就达到标准的状态转移
再输入b 就转移到q1
q1再输入b 就转移到q2
这样我们通过前面的递归的形式
就可以求出这样一个q0 输入一个串ab
它转移到最后转移到q2
这个结果跟这是一样的
这是前面我们介绍的一个状态转移图
它对应的是状态转移表
那经过扩展的状态转移函数
在q0输入空串 它到q0
输入0 它就到q2
输入串00 它到q0
输入串001它 到q1
输入串0010 到q3
通过这个定义可以看出
状态转移
不但是通过一个状态和一个输入字符
可以转到另外一个状态
还可以通过一个状态输入一个串
达到一个状态的转移
这就给我们提供了
下一节自动机语言的一个定义
这节内容讲到这里
谢谢大家
-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
-习题--作业
-期中考试