当前课程知识点：软件理论基础 > 第十章 下推自动机与CFG化简规范 > 10.2 DPDA与其他语言的关系 > Video
欢迎同学们来到《软件理论基础》的MOOC课堂
现在介绍确定下推自动机的语言
DPDA语言与其它语言之间的关系
回顾我们在第二章里面我们讲的DFA和NFA
虽然这两类自动机 它的结构不一样
但是我们之后证明了
这两类自动机 它的语言是相同的
也就是它们两类自动机是等价的
那我们现在介绍了PDA 也介绍了DPDA
那这两类自动机 它们是不是相同的呢
首先我们知道这个DPDA
通过它的定义
它实际上是满足我们的PDA或者NPDA的
所以DPDA的语言就不论是空栈型的语言
还是终态型的语言
它都包含在上下无关语言里面
也就是NPDA这个语言当中
这个包含是成立的
那它们这个是不是相等的呢
我们下面看这个例子
这是我们的上一节里面介绍过
这样的一个回稳语言
这个语言在我们讲PDA的时候我们讲过
这个语言它是一个PDA的语言
也是上下无关语言
但是这个语言它是没有DPDA接受它的
那从这个例子我们就看出DPDA与PDA之间
它们是有差异的
存在语言它是属于这个上下无关语言的
但是这个语言它是不属于DPDA语言
这个事实就告诉我们
DPDA的语言
它是真包含在NPDA这个语言当中
它们两个是不相等的
换句话说NPDA就是上下无关语言
它的表达能力比DPDA的表达能力要强
下面我们再看看DPDA
它与正则语言之间的关系
我们下面有这个定理
如果L是正则语言
一定存在一个DPDA这个自动机
它接受这个语言
这个结论就说明
正则语言 一定是DPDA的语言
因为L是正则语言
我们在第二章里面介绍过
正则语言它一定有一个DFA来接受它
我们假设这个DFA是这个自动机
我们就根据这个DFA就确定有限自动机
来构造一个DPDA
这个构造实际上很简单
我们的状态输入字母
初始状态在终态
都按这个DFA来给出
栈在这里只是一种象征性的作用
它没有实质性的
也就是说我们在这里定义状态转移的时候
这个状态转移到这里
当且仅当在DFA里面有这个转移
它们接受的语言是相同的
这就说明正则语言一定是DPDA的语言
那反过来是承认吗
也就是说DPDA的语言是不是正则语言呢
从我们前面讲过一个例子
这个语言
这个语言我们可以用泵引理证明
它不是正则语言
这样的一个确定下推自动机接受它
所以它是一个DPDA的语言
实际上我们在开始也讲过一个例子
0的n次方 1的n次方
这个语言它不是正则语言
但是它是DPDA的语言
这就说明DPDA的语言
它的表达能力要比正则语言
或者比有限自动机表达能力要强
这节里面我们介绍了
DPDA的语言与正则语言
DPDA的语言与PDA的语言
它们之间的关系
在下节里面我们还要讨论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
-习题--作业
-期中考试
