当前课程知识点：软件理论基础 > 第十章 下推自动机与CFG化简规范 > 10.1 确定下推自动机 > Video
欢迎同学们来到《软件理论基础》的MOOC课堂
我是清华大学教师罗贵明
今天我们介绍的内容是DPDA
我们的内容包括概念
DPDA语言与其他语言的关系
最后讲终态型DPDA与空栈型DPDA
首先我们介绍确定下推自动机
我们先回顾一下
在这门课第二章里面
我们介绍的有限自动机
在那里面我们介绍了DFA和NFA
只不过在那里面
我们首先是介绍了确定有限自动机
之后我们再介绍非确定有限自动机
而在下推自动机里面
我们是首先介绍非确定下推自动机
然后我们再介绍确定下推自动机
那什么是确定下推自动机
我们首先看看定义
给一个下推自动机
这是一个七元组 是带终态的
如果这个下推自动机 我们也称DPDA
它满足下面这种条件
对输入字母A或者也可以是空串
我们这个栈符号它不为空的
那如果这个状态转移
它最多只包含一个元素
还有下面第二个条件
对于输入字母a
a它可以为空 也可以不为空
如果这个状态转移它不为空的话
这个输入字母为空串的
它一定是为空
这个输入的字母a和空串
它们是互斥的
特别我们强调是在栈符号
我们之前在定义PDA的时候
这个栈符号可以为空串
但是在DPDA里面
我们的栈符号一定是不为空的
类似的我们也可以定义空栈型DPDA
也就是说我们只是在原来的PDA里面
把它改为空栈型的PDA
在这个DPDA里面 哪些转移是允许的
在状态q1 我们输入a
栈底符号b 换为一个字符串w
它转移到q2 这个转移是可以的
或者在q1这个状态
我们也可以输入空串
把b换成w 转移到q2
像这些转移它都是确定的
那下面这样的转移也是可以的
在q1状态我输入a
栈顶符号是b把它替换为w1
然后到状态q2
或者栈顶符号c替为w2
到q3这个状态
这个都是可以的
在这种情况也是可以
我的输入都是空串
栈顶符号b换为w1
状态改为q2
栈顶c把它换为字符串w2 然后到q3
这些转移都是确定的
那在这个DPDA里面哪些是不允许的
下面我们看这样的状态转移
对状态q1相同的输入字母a
栈顶符号都是b的时候
我把这个b换为w1转到q2
我又把这个b换成w2转为q3
这类转移在我们DPDA里面是不允许的
下面这种情况也是不允许的
在q1输入空串
把b变成w1到q2
同时在q1这个状态输入a
把b换为w2到q3
这个也是不允许的
这个都是非确定情形
特别是对这种情形
我们强调的是输入字母a和空串
是不能同时出现的
下面我们看一个例子
这个自动机有四个状态
但这个自动机大家应该是挺熟悉的
我们实际上在之前
已经介绍过这个类型的
这个自动机它是有终态
我们这里是输入一个0 压一个0
然后输入一个1弹出一个1
如果是输入串输入完了
栈是栈顶符号 我们找终态
那我们再看这个自动机
这也是四个状态
其他的情形都跟这个类似
只是这里是终态
而这个地方它是一个非终态
但是我们这里
是把一个栈底符号弹出来了
这两个自动机根据我们之前讲PDA
它接受的语言的话
实际上这两个自动机
它接受的语言都是0的n次方
1的n次方
那我们下面就定义什么是DPDA的语言
首先我们定义终态型DPDA的语言
如果有个语言
它能够被一个终态型的
或者我们也叫DPDA
这里下推自动机能够接受的话
那我们就称这个语言
是确定性下推自动机的语言
或者也叫确定性上下文无关语言
或者也叫做终态型DPDA的语言
像我们上面讲的这个例子
这个语言 它就是一个终态型DPDA的语言
那还有另外一类DPDA叫空栈型DPDA语言
那这个定义是如果一个语言
能够被一个空栈型的DPDA来接受的话
那这个语言就称为空栈型的DPDA的语言
那像我们上一个例子里面这个语言
它有一个空栈型DPDA接受它
所以它就是一个空栈型DPDA的语言
我们前面还介绍过这样一个下推自动机
这个下推自动机
它接受的语言应该是WWW翻转
也是一个回稳
这个下推自动机
你看它有一个这样的一个转移
输入空串
这个栈顶符号是空串不变
再到另外一个状态
这个地方在做转移的时候
它每次有两种选择
也就是说这是一个非确定的
在这个地方
PDA里面是可以的
在DPDA里面是不允许的
实际上我们可以证明
实际上我们是找不到一个DPDA
来接受这个语言的
也就是说WWW翻转
这个语言它不是DPDA的语言
上面我们介绍了另外的一类下推自动机
叫确定下推自动机
好 这节内容介绍完毕
谢谢大家
-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
-习题--作业
-期中考试
