当前课程知识点：软件理论基础 > 第十一章 上下文无关语言的性质 > 11.4 CFL的同态性质 > Video
欢迎同学们来到《软件理论基础》MOOC课堂
现在介绍上下文无关语言
性质的第四个部分
上下文无关语言的同态性质
首先介绍上下文无关语言的替换
假设∑是一个字母表
这个花L是一个语言的集合
它的元素都是语言
有一个映射s
是字母表到这个语言集合的映射
对任何一个a属于这个字母表
映射的象s(a）属于这个花L
是一个语言
称这个映射是一个替换
这是字母表到语言集合的一个替换
下面对这个概念进行扩展
假设∑*是这个闭包
这里面元素都是串
s是串到这个语言中的一个映射
对任何一个串
每一个字母对应的语言
每一个字母对应的语言
这些语言作连接
也是这个串到语言中一个映射
假设 L是∑上的一个语言
定义语言的一个映射
原来是字母表
后来到它的串的集合
再到语言
这个语言
因为语言都是由一些串构成的
对任何一个串
这里已经给出定义
这样，每一个串得到一个语言
把所有这语言
因为语言是集合，它们并起来
就得到这个语言的一个映射
或者这上面的一个替换
看一个例子
假设输入字母是0和1
替换是这样给的
把0映射成{a的n次方、b的n次方}
这是一个语言
1替换为{abb}，这是另外一个语言
这是字母表到语言中的映射
再看这个串
w=01
这个串在替换下，是 s(0)s(1}
串是01
得到这两个语言的连接
这个语言代进
得到这样的连接
如果给这一个语言
是 {0*}
在这替换下，s(L) 这个语言中
任何一个串
得到的语言，然后作并
是这语言的“*”闭包
得到的语言
它的元素是这样的
这就是上下文无关语言的替换
得到的性质
有下面定理
假设S是∑输入字母上一个替换
对任何一个输入字母
它的像是一个上下文无关语言
假设L是∑上的一个上下文无关语言
S对L映射
它的像也是一个上下文无关语言
证明这个结论，任何一个串
都有一棵语法分析树生成它
这棵语法分析树是怎么得到的呢？
因为L是一个上下文无关语言
对于任何一个串
应该有一个以S为根结点的
一棵语法分析树
这个串假设是a_1a_2 ... a_n
得到a_1a_2 ... a_n的一棵语法分析树
而a_1这一个输入字母
在s的映射下
它是一个上下文无关语言
因为s(a}都是上下文无关语言
下面就有一棵子树
s(a_2)也有一棵子树
s(a_n)也有一棵子树
子树产生的这些产物
就是整个的s(L)
它的语法分析树的产物
这就证明了s(L)
它的任何一个串，都有一棵语法分析树
这就证明了s(L)也是一个上下文无关语言
根据定理
可以证明上下文无关语言的它的同态
具有这个特点的映射
就是一个同态映射
这样的h
跟前面讲的替换s非常相像
它是s中一个特殊情形
定理的h是一个替换
适用于语言L
根据之前的定义，得到的像
可以证明这个h
是L上的一个同态映射
h是一种特殊的替换s
根据前面的定理
如果L是一个上下文无关语言
这映射是同态映射
得到的像h(L)
也是一个上下文无关语言
上下文无关语言的逆同态
之前讲的正则语言逆同态
上下文无关语言它的逆同态
怎么定义呢?
假设h是同态映射
语言是T中的一个语言
像集中的一个语言
把像集中这个语言
逆像过去
就是h(w），它属于这L
w的原像
得到的是语言L的逆像
跟逆映射的逆像是一样的
定理
如果L是T*中
一个上下文无关语言
h是一个同态映射
L的逆映射，也就是映射
同态映射的逆像，也是一个上下文无关语言
证明这个结论，可以用构造方法
假设L是一个上下文无关语言
它就对应一个下推自动机
根据这个下推自动机
对应L的下推自动机P
构造它的逆像的下推自动机
逆像的下推自动机用P'表示
P' 的输入字母、栈符号
栈底符号，跟P是一致的
只是状态集做了一些改进
对任何一个输入字母a
新的状态转移
把原来状态，这个前缀
都压到新的状态里
利用这种方式
它的输入字母，一个个消掉
运作可以通过这个下推自动机结构
可以分析
这样构造的
下推自动机P'
可以证明，得到的语言
就是这个逆同态语言
就证明了，这个语言的逆同态
也是一个上下文无关语言
这节里介绍了
上下文无关语言同态映射下
得到的像是上下文无关语言
对于同态映射，一个上下文无关语言
它的逆像也是一个上下文无关语言
这些性质跟之前介绍
正则语言的性质是类似的
这节内容介绍完毕
谢谢大家
-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
-习题--作业
-期中考试
