当前课程知识点：软件理论基础 > 第九章 下推自动机 > 9.3 PDA的即时描述 > Video
欢迎同学们来到《软件理论基础》的MOOC课堂
现在介绍下推自动机的即时描述
什么是下推自动机的即时描述呢
因为我们很关注的
下推自动机当前的格局
当前的格局
可以用这一个三元组来表示出来
三元组q表示当前的状态
w表示我们剩下的
还没有读的那些输入
栈里面还有一些什么符号
对下推自动机来说
这三个符号是非常关注
如果知道了当前状态
还有没有读完的输入
栈里面什么符号
实际上我们对下推自动机
它当时所处的格局是非常清楚的
对于当前的格局
还要对下一个格局之间有一种关联
这种关联就是传递
假设这是给了一个下推自动机
如果是在这个下推自动机里面
做传递的话
我们底下标上这个p
如果是很清楚这个下推自动机
我们可以把这个p把它去掉
在下推自动机里面有这样一个状态转移
这个状态转移当前的状态是q 要输入a
栈顶是x
把x并为一个串α转到新的状态p
也就是我们这非确定的情况
是用这么一个输入
如果是这样一个即时描述
这个即时描述是三元组
当前状态是q
剩下的输入是aw
栈顶符号是xβ
那经过这样的一个状态转移
那这个时候
我们这个即时描述在这个状态转移之后
得到了新的一个即时描述
大家看应该是什么呢
应该是这样的
这个p
我这个输入用完了还剩了一个w
栈里面就变成了αβ
从这一个即时描述到这个即时描述
是这个状态转移得到的
我们这个传递就是从这个即时描述
传递到这个
那其中其他的符号我们按这里记
如果是只关注我们最后传递的结果
而不考虑中间每一步传递的步骤
那下面我们就讲到
即时描述的传递闭包
即时描述的传递闭包
记号跟刚才记号是一样的
型号表示的
我们是用归纳来定义这个传递闭包
对于任意的即时描述我们用I表示
就是任何的即时描述I
它可以传递闭包到I这是我们的基础
零部的这种传递我们也叫推导
归纳如果I经过一次传递到K
K是即时描述
而这个K这个即时描述
经过若干步我们再打一个*
到另外一个即时描述J
那我们就可以记成I这个即时描述
它也经过若干步能够传递到J
这个即时描述
这种定义的形式在之前我们用过多次
下面我们看一个例子
在前面我们讲过这个下推自动机
我们说它对这个输入来说
第四次的这个转移
它还是在这个状态
读这个a 这是第四次转移
栈里面压了三个a
这个即时描述该怎么表示呢
因为当前的状态是q1
剩下的输入还有bbb
栈里是这些符号
那我们这个即时描述
就可以表示成这种形式
那我们再看第五次的这个转移
第五次也就读这个b
我们就得到栈里面还剩下这些
状态是这个
而剩下的输入是这个
也就是我们的即时描述是这样表示的
那第四次即时描述到第五次即时描述
这个转移就可以这样表示了
你看这个即时描述实际上
它可以表示整个格局的一个变化
那我们下面有这样一个定理
给了一个下推自动机
如果有这样的一个即时描述的转移
那下面对这样的即时描述
这个即时描述跟这个有点类似
但是它剩下的输入串要比它多一个w
栈里面要比它多一个г
那在这个转移下面
这个即时描述该是什么结果呢
通过归纳可以推出来
这个即时描述经过若干步
实际上可以转移到这种即时描述
这就证明我们刚才说的
是通过这个传递的步数做归纳就可以了
下面我们看这个串
在这个自动机里面做即时描述的
它的整个的这个转移
我们可以通过传递闭包把它表示出来
首先我们写的即时描述是q0
把这个串写这里
最开始栈里面写栈底符号Z0
经过若干次推导
我们说是第四次推导
就得到这个即时描述
再通过若干次推导
实际上最后推导了到了这个即时描述
这个即时描述q2是这个
串读完了
栈里面是那个栈底符号Z0
之后再用这个状态转移
得到这个即时描述
这个即时描述就是q3这个状态 空串
输入是空串
栈里面是Z0
对这样一个即时描述
在这个自动机里面经过若干次转移
最后转移到这里来
我们前面讲了这个串
是被这个自动机接受的
从这里即时描述的这个转移
这个即时描述最后转移到它
也可以刻划出这个串
被接受的这个特性
这就是我们之后要介绍下推自动机
这个语言的形式化定义该怎么给
好 这节内容介绍到这里
谢谢大家
-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
-习题--作业
-期中考试
