当前课程知识点:软件理论基础 >  第十一章 上下文无关语言的性质 >  11.5 CFL的交运算 >  Video

返回《软件理论基础》慕课在线视频课程列表

Video在线视频

下一节:Video

返回《软件理论基础》慕课在线视频列表

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

-习题--作业

第六章 正则语言的性质与DFA优化

-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

-习题--作业

第八章 CFG的应用与文法的二义性

-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

-习题--作业

第十章 下推自动机与CFG化简规范

-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

-习题--作业

第十二章 Turing机

-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

-习题--作业

期中考试

-期中考试

Video笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。