当前课程知识点：软件理论基础 > 第十一章 上下文无关语言的性质 > 11.3 CFL的闭运算性质 > Video
欢迎同学们来到《软件理论基础》MOOC课堂
现在介绍上下文无关语言性质的第三部分
上下文无关语言的闭运算性质
在之前讲到了
怎样去判定一个语言是上下文无关语言
要么是把它的文法
上下无关文法给出来
要么把它的下推自动机给出来
这个语言就是一个上下文无关语言
是不是任何一个语言
都按这种判定呢?
有时候可以通过语言本身的性质
来推导它，这样更容易些
如同之前讲正则语言的
闭运算性质一样
对上下文无关语言
也有一些基本运算
这些运算包括并、闭包、连接、反转
首先看上下文无关语言的并
L假设是一个上下文无关语言
M也是一个上下文无关语言
它们的并是不是还是一个上下文无关语言呢？
有下面的定理
如果L和M它们都是上下文无关语言
它们的并也是一个上下文无关语言
这跟正则语言的并运算是类似的
大家回顾一下
当时讲正则语言并的时候
是利用两个自动机
证明这个性质的
现在讲上下文无关语言
就不用下推自动机
用另外一种方法
首先看一个例子
假设给了这个语言
a的n次方，b的n次方
它的文法可以这样来产生
再给另外一个语言ww的反转
它的文法是这样的
这个语言对应上下无关文法
这两个语言的并
怎么把这个并语言
它的文法给出来呢？
只需要增加一个开始变量S
增加产生式：S产生S1
再增加一个产生式：S产生S2
然后把这两个文法放在下面
就得到这个并语言的上下无关文法
一般的上下文无关语言
也可以这样处理
假设一般的上下文无关语言L1、L2
它们对应的上下无关文法是G1和G2
它们的开始变量
L1对应的文法的开始变量是S1
G2的开始变量是S2
下面讨论这两个语言的并
增加一个开始变量S
然后再增加两个产生式
S产生S1
S产生S2
再把G1文法放在下面
G2文法产生式放在下面
这样得到了新的一个文法
就是并语言的文法
这证明非常简单
就得到任何两个上下文无关语言
它们的并仍然是一个上下文无关语言
再看
上下文无关语言的闭包
主要是指“*”闭包和“+”闭包
假设L是一个上下文无关语言
它的“*”闭包和“+”闭包
是不是还是上下文无关语言呢？
有这样的定理
L是一个上下文无关语言
这两类闭包都是上下文无关语言
看一个例子
L1是前面给的一个语言
a的n次方、b的n次方
它的文法是这样的
讨论它的“*”闭包
这个语言的*闭包
只需要增加一个开始变量S1
增加两个产生式： S1产生SS1和S1产生ε
再把这个文法的产生式放在下面
这样得到的文法
就是这个语言“*”闭包它的文法
一般情况下，假设L
是一个上下文无关语言
它对应的上下无关文法是G
开始变量是S
讨论这个语言的“*"闭包L*
只需要增加一个开始变量S1
再增加两个产生式： S1产生SS1和S1产生ε
再把原来的文法G 的产生式放在下面
构成了一个新的文法，就是
L*的上下无关文法
因此，对任何一个上下文无关语言
它的"*"闭包仍然是上下文无关语言
对"+"闭包类似证明
再看上下文无关语言的连接
假设L、M都是上下文无关语言
它们的连接是不是还是上下文无关语言？
定理
上下文无关语言的连接依然是上下文无关语言
例子
这是前面给的语言
它们对应的文法
它们的连接得到的语言
只要增加一个开始变量S
增加一个产生式：S产生S1S2
然后把这产生式放在下面
得到的文法就是
两个语言连接的语言
的上下无关文法
对一般的情形
L1、L2，假设它们是上下文无关语言
对应的文法分别是G1、G2
开始变量分别是S1、S2
这两个语言的连接
我需要增加一个开始变量
增加一个产生式：S产生S1S2
然后把G1和G2
文法的产生式放在下面
构成的新文法
就是两个语言连接的上下无关文法
这就证明了两个上下文无关语言
它们的连接得到的语言依然是上下文无关语言
最后，看上下文无关语言的反转
前面已经定义了一个语言的反转
假设L是一个上下文无关语言
它的反转是不是还是一个上下文无关语言呢？
结论是肯定的
上下文无关语言的反转也是上下文无关语言
证明这个结论
是利用构造的方法
假设L是上下文无关语言
对应的上下无关文法G是这类种形式
通过G构造另外一个文法G的反转
就是GR
这个文法变量跟G的变量一样
终结符集合也是一样
开始变量跟它是一样
只是产生式发生了一些改变
P的反转
P的反转是根据P构造的
只要P中有：A产生α
P的反转就有：A产生αR
也就是α的反转
这个串的反转
这样，得到的文法GR
可以证明，这个文法的语言
就是原来语言L的反转
证明很简单
大家可以做练习完成
这节介绍了
上下文无关语言的几个基本运算
并、连接、闭包、反转
上下文无关语言对这些运算都是封闭的
这节内容介绍完毕
谢谢大家
-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
-习题--作业
-期中考试
