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

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

Video在线视频

下一节:Video

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

Video课程教案、知识点、字幕

欢迎同学们来到《软件理论基础》的MOOC课堂

现在介绍上下文无关语言性质的第二节

也就是上下文无关语言的泵引理

在上一节里面已经介绍了

上下文无关语言的一个必要条件

通过这个必要条件

可以得到上下文无关语言的泵引理

通过这个定理来叙述

假设L是一个上下文无关语言

一定存在一个常数n,正的常数n

对于任意的串z属于L

只要是z大于等于n

z一定可以表示成为uvwxy五个部分

这五个部分它满足下面的条件

第一:vx当中至少有一个为空串

第二:vwx串的长度

小于或等于存在这个n

最后:对任意的k,

u、v的k次方w、x的k次方、y,这样得到的串

都应该在这上下文无关语言里

这就是上下文无关语言的泵引理

要证明这一点

可以通过两方面:

首先,如果这个语言是空集或者是空串

当然,随便找一个大于或等于n

这个串就没有了

所以,证明这是成立的

如果这个语言是个无限语言

就可以用上一节讲的必要条件

只取这n等于2的|V|次方

V 是变量的个数

实际上任何大于或等于这样一个数的

一个正整数

都可以当做这个n

就可以通过上节个必要条件

来证明这定理

泵引理

也可以把它表示成为逻辑形式

存在一个正整数n

对任意的这语言中的串

这个串的长度就大于或等于n

这个串就一定能够写成这五部分

它满足:vx不等于空串

|vwx| 小于或等于n

对于任意的k

得到u、v的k次方、w、x的k次方、y

都应该属于这上下文无关语言

这就是前面泵引理的逻辑形式

这种形式或者这个命题的否命题

跟之前的正则语言一样

大家根据逻辑知识,很容易得到

根据这否命题

就发现泵引理是干什么用的

是用于证明一个语言不是上下文无关语言

证明一个语言是上下文无关语言

要么把它的(CFG)文法能够写出来

一个上下无关文法

要么把它的下推自动机能够画出来

能够表示出来

这个语言就是一个上下文无关语言

要证明一个语言不是上下文无关语言

这跟之前要证明一个语言不是正则语言

直接证明是没办法

下面就用这泵引理

来证明一个L不是上下文无关语言

要证明一个语言不是上下文无关语言

它的步骤:根据前面讲的泵引理的否命题

可以把它写成这种步骤

第一:任意的选取正整数n

第二:找L中一个字符串

这个字符串必须满足下面的条件

这字符串的长度要大于或等于n

对于任意满足这样一个表示:uvwxy

其中,vx是不于等空串

vwx 长度是小于或等于n的

然后,选择一个k

使得u、v的k次方、w、x的k次方,y 不在这语言里

如果找到了

这个语言一定不是上下文无关语言

用泵引理的否命题

说明了这个事实

下面用这个方法

证明一个语言不是上下文无关语言

首先看这个例子

这语言输入字母是0、1、2

它表示是0的k次方

1的k次方、2的k次方

这样得到的串当然是一个无限语言

它不是上下文无关语言

怎么证明呢

采用刚才讲的上下文无关语言的泵引理

根据步骤

首先,对任意正整数n

这个n是任意的

在这语言中

要找长度大于或等于n的一个串

因为这个语言中的特征是:0

0是k个

1是k个

2是k个

要按这个特征,描写长度不小于n的

这在证明中非常重要一步

就看这个串写的对不对

写这样一个串

z等于0的n次方、1的n次方、2的n次方

这个串肯定在这个语言中

这个串的长度是3n

它是大于n的

对这个串

任意的分

分成五个部分 u、v、w、x、y

只要vx不等于空串

vwx 长度小于等于n

任意的写

大家看

由于vwx 长度

是小于或等于n的

这1的个数是等于n的

因此

v、w、x不可能既取得0、 取得1、 又取得2

因为1的个数就等于n

由于z不能全部取得0,1,2

选取k等于0

把v取成0个数

x也取0个数

这是空串

由于v、x至少有一个不等于空串

在这个0、1、2中

必须要消除一些字符

但是,不可能0消除的字符个数

跟1消除的字符个数

跟2消除的字符个数是相同的

这是不可能的

因为它们不可能同时取得0、1、2

这就说明,这得到的uwy

不在这语言里

因为这个语言里0的个数、1的个数、2的个数

都是相等的

通过泵引理证明了这个语言

不是上下文无关语言

通过这个方法就证明了

这类语言不是上下文无关语言

下面再看一个例子

证明ww这个语言

这输入字母是0、1

它不是上下文无关语言

这语言前面是一个串

后面这个w跟它是相同的

记得之前讲上下无关文法的时候

曾经讲过一个语言

不能表示成为ww串的这类语言

反而是一个上下文无关语言

可以把它的文法构造出来

现在是ww

它不是一个上下文无关语言

怎么证明呢?

还是按照

上下文无关语言泵引理的方法

首先,选取任意的正整数n

接下来要选取这语言中的一个串

长度大于或等于n

怎么选取?

因为这里输入字母是0、1

串必须前面一部分是w

后面一部分还是w

而且长度必须大于或等于n的

选取的话

选取这样的一个特殊串

0的n次方、1的n次方,就是w

接下来重复它

0的n次方、1的n次方

这串在这个语言里

长度等于4n

是大于n的

对这个串,任意的分

把它写成为u、v、w、x、y

任意的写

只要满足v和x至少有一个不等于空串

|vwx| 是小于或等于n的

由于|vwx| 是小于或等于n的

说明vwx不可能取到0、1、0、1中

字符里所有的字符

因为1的个数是n个

0的个数是n个

不可能从这里取

跟刚才的分析一样

选取k等于0

k等于0,就把v和x去掉了

因为vx不等于空串

必然

有的或者是0、或者是这里面1

或者这个0、或者是这里面1

必须消除

但是不可能

这里面消除了

这里面消除了

这里面消除了

这里面消除了

完全是相同的

这样就证明了

根据泵引理证明了这个语言

不是上下文无关语言

这节介绍了

上下文无关语言的泵引理

而且通过泵引理证明了一些语言

不是上下文无关语言

这节内容介绍完毕

谢谢大家

软件理论基础课程列表:

第一章 基础知识

-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笔记与讨论

也许你还感兴趣的课程:

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