当前课程知识点:软件理论基础 > 第十一章 上下文无关语言的性质 > 11.5 CFL的交运算 > Video
欢迎同学们来到《软件理论基础》MOOC课堂
现在介绍上下文无关语言性质的第五节
上下文无关语言的"交"运算
在前面两节里介绍了
上下文无关语言的一些闭运算性质
在语言的运算里,还有一个运算
“交”运算
没讲
上下文无关语言的交是不是封闭的呢?
给了两个语言
L、M都是上下文无关语言
它们的交,是不是还是上下文无关语言?
在正则语言里,这个结论是成立的
但是对于上下文无关语言来说
不一定成立
两个上下文无关语言的交
不一定是上下文无关语言
要证明这个结论
只需要找一个反例就可以了
L1是{a^nb^nc^m}
L2是{a^nb^mc^m}
L1对应的文法
L2对应的是这个文法
这两个文法都是上下无关文法
因此,这两个语言都是上下文无关语言
这两个语言它们的交
是{a^nb^nc^n}
这个语言,在第二节里
证明了它不是上下文无关语言
由此说明两个上下文无关语言
它们的交不一定是上下文无关语言
有了这样一个结论
还可以推出两个上下文无关语言
它们的差
也不一定是上下文无关语言
只需这个性质
再用德摩根公式,马上得到这结论
两个上下文无关语言的交
不一定是上下文无关语言
上下文无关语言与一个正则语言的交
有一个比较好的性质
定理
L假设它是上下文无关语言
R是正则语言
这两个语言的交是上下文无关语言
要证明定理,只需要采用这样构造
因为R是正则语言
它就有一个DFA接受这个语言
L是上下文无关语言
它就有一个PDA
P接受这个语言
下面构造一个PDA,称为p'
自动机的输入字母、栈符号、栈底符号
跟前面的自动机 P 是一致的
状态集是这两个状态集的笛卡尔积
初态和终态
分别是它们初态和终态的笛卡尔积
这样构造的一个下推自动机
可以证明它接受的语言
就是这两个语言的交
自动机 δ 是由这两个自动机
它们的状态转移确定
新自动机的状态转移
(q,p)输入a
栈顶符号为x
转移到新的状态 (r,s) ,栈改为γ
转移按照前面的下推自动机
和前面给的DFA确定
根据这样的转移,可以证明
得到的下推自动机
它的语言就是一个上下文无关语言
与正则语言的交
还可以把“交”来构造
用下面结构
假设这是一个上下文无关语言
对应一个PDA M
这是一个正则语言,它对应一个DFA
要构造这两个语言的交M
用这样的方法构造
在PDA里,假设有这样的转移
在DFA里,有这样的转移
在新的PDA里,就有这样的转移
大家注意
PDA是非确定的下推自动机
DFA是确定有限自动机
非确定的包含有ε输入
而在DFA没有ε输入
这样情况该怎么构造?
PDA有ε输入,是这样的转移
DFA里没有
新的下推自动机,对ε输入
q1,让下推自动机这个转移
p1,它不变
这样得到的转移
就是新的下推自动机的转移
新的下推自动机的初态
就是原来两个自动机初态的笛卡尔积
终态是子集
是两个下推自动机
它们终态子集的笛卡尔积
这就构造出一个上下文无关语言
与正则语言交的下推自动机
例子
这个语言的输入字母是{a,b,c,d}
串前缀是w1
w1在{a,b}取值
后缀w2在{c,d}取值
,
要求w1的长度跟w2的长度相等
对这个语言
怎么证明是上下文无关语言?
如果把它的文法写出来
或者是下推自动机画出来就可以了
这个语言的下推自动机
是这样一个下推自动机
当然,它是一个上下文无关语言
再看另一个语言
L2等于{a,c}*
它的自动机,这是DFA
因此是正则语言
一个上下文无关语言
与这正则语言
它们的交是a的n次方、c的n次方
它的语言大家熟悉
是一个上下文无关语言
这个例子验证了刚才的结论
L1假设是上下文无关语言
L2是正则语言
前面证明了
它们的交是一个上下文无关语言
这个性质也称为正则“闭性质”
利用这个性质
可以解决后面的一些问题
下面看例子
这个语言是:a的n次方 b的n次方
但n不等于100
如果没有这个要求
这个语言大家太熟悉了
它是一个上下文无关语言
它的文法或者PDA很容易构造
现在n不等于100
证明它也是一个上下文无关语言
结论看似显然
怎么证明它是一个上下文无关语言呢?
分析:这个语言a的n次方 b的n次方
它是一个上下文无关语言
另外,a的100次方b的100次方
是一个有限串
可以用一个DFA表示它
因此是一个正则语言
虽然上下文无关语言的补运算
不一定封闭
但正则语言的交运算
补运算都是封闭的
因此,这个语言是正则
推出补语言也是正则
这是一个上下文无关语言
这是一个正则语言
两个语言的交,根据前面的性质
就是一个上下文无关语言
这交是什么?
就是前面给的语言
这样,就证明了给的语言
是一个上下文无关语言
再看一个例子
这个语言的输入字母是{a,b,c}
这表示,这个串中a的个数
这个串中b的个数
这个串中c的个数
这些个数都是相等的
我们并不关心这个串字母的次序
只要个数相等就OK了
证明这个语言它不是上下文无关语言
当然可以用泵引理证明
用另外的方法来证明
要证明它不是上下文无关语言
假设这个语言是上下文无关语言
因为语言:{ a的"*"闭包
b的"*"闭包
c的"*"闭包 }
是一个正则语言
假设这个语言是上下文无关语言
它是一个正则语言
根据前面的
介绍的正则“闭性质”
这两个语言的交
应该是一个上下文无关语言
它们的交是什么?
是{a的n次方 b的n次方 c的n次方}
前面证明了
它不是一个上下文无关语言
得出错误的结论
错误的结论
主要是假定了这个语言
是上下文无关语言
由此证明了给的这个语言
它不是上下文无关语言
在这节里
给出了上下文无关语言交的一些性质
上下文无关语言对交运算不封闭
也就是说,两个上下文无关语言的交
不一定是上下文无关语言
但上下文无关语言与正则语言的交
它一定是一个上下文无关语言
这节内容介绍完毕
谢谢大家
-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
-习题--作业
-期中考试