当前课程知识点:软件理论基础 >  第二章 确定有限自动机 >  2.3 扩展转移函数 >  Video

返回《软件理论基础》慕课在线视频课程列表

Video在线视频

Video

下一节:Video

返回《软件理论基础》慕课在线视频列表

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

-习题--作业

第六章 正则语言的性质与DFA优化

-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

-习题--作业

第八章 CFG的应用与文法的二义性

-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

-习题--作业

第十章 下推自动机与CFG化简规范

-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

-习题--作业

第十二章 Turing机

-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

-习题--作业

期中考试

-期中考试

Video笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。