当前课程知识点：软件理论基础 > 第十一章 上下文无关语言的性质 > 11.1 CFL的必要条件 > Video
欢迎同学们来到《软件理论基础》MOOC课堂
我是清华大学教师罗贵明
今天介绍的内容是上下无关语言的性质
内容包括有CFL
（也就是上下无关语言）的必要条件
CFL的Pumping引理
CFL的闭运算性质
CFL的同态性质
CFL的交运算
最后介绍CFL的判定性质
首先介绍上下无关语言的必要条件
大家回顾一下
在上一章里面我们介绍了
上下无关文法的简化以及文法的规范
也就是Chomsky范式
Chomsky范式第一个特点就是
它有很好的文法结构
因为Chomsky范式它只有两类产生式
它的语法分析树就是一个二叉树
它的文法结构非常好
第二个性质就是任何一个上下无关文法
都能容易的转化为Chomsky范式
如果一个文法转化为Chomsky范式很难
那接下来分析也是没有多大的用处了
Chomsky范式
它可以用于文法的解析
以及后面的定理证明
下面我们介绍上下无关语言的
一个必要条件
大家再回顾一下
之前我们介绍正则语言的时候
也介绍了一个必要条件
当时，我们利用正则语言与一个DFA对应
然后利用鸽巢原理求出
正则语言的一个必要条件
现在讲了上下无关语言
而且上下无关语言它也与一个自动机
下推自动机对应
是不是我们也可以按照之前
正则语言的那种思路
通过下推自动机来求出它的一个必要条件
大家注意下推自动机有一个栈
栈可以读和写
这种操作它有别于DFA
按照这种方法来求它的必要条件是行不通的
下面我们用什么方法去求
上下无关语言的必要条件呢？
我们就想到了之前的Chomsky范式
假设这个语言L
它是一个无限的上下无关语言
它就对应一个Chomsky范式
我们假设这个Chomsky范式
给定的这个文法
它的变量的个数为m
记n等于2的m次方
对于任何的这个语言当中的一个串z
现在就考虑z它的分析树
假设这个z它的分析树的高度为m
也就是它的最大的一个路径长度为m
知道这个二叉树
由语法分析树得到的产物z
它的长度就是小于或等于2的m-1次方
当然是小于这个n的
假设这就是它的一个最大长度
如果给出这个z
它的长度是大于或等于2的m次方
我们就知道
这个语法分析树的高度至少为m+1
假设这就是语法分析树
最长的一个路径
这里有变量A0、A1、A2、...、AK
最后一个产生式，就生成终结符a
因为它高度为m+1
那前面这个变量 它的A0、A1、A2、...、AK
这个k就必然要大于和等于m
m+1个变量
现在找的变量
是从它的路径里找
因为m是变量的个数
因此，在这个路径
前面给的这些变量当中
不同的变量只有m个
这就得到了
在这些变量当中
至少有两个变量是相同的
变量是从最后到前面找
m+1一个变量
从最后向前找的m+1个变量
而且找第一个出现相同的变量
把它记为Ai
就是Ai等于Aj
i是小于j的
语法分析树中
这个路径上搜索两个相同变量，从下往上搜
第一个出现重复的变量是Ai
Ai是跟Aj是相等的
有了这样分析之后
分别以A是根结点的
以Ai为根结点的
以Aj为根结点的
这里语法分析树它们分别的产物
以S为根结点的产物就是整个z
以Aj为根结点的产物
假设它是w
以Ai为根结点的子树
它的产物就是vwx就构成的串
其中v在w它的左边
x在w的右边
由于这是Chomsky范式
它没有单一产生式
那也就说,Ai不会通过单一产生式推出Aj
或者Ai推出Aj
没有这样的产生式
v或者x子串
至少有一个是不为空串的
如果它们都是空串
这里就会出现单一产生式了
也就是说，vx这个串
它是不等于空串的
我们再看看，因为Ai它是
就是从下往上
第一个出现重复的变量
从Ai得到的产物
它最长的长度应该是小于2的m次方
也就是小于或等于n
从这里推出
这个分析树的一个性质
然后,我们继续观察
如果把Ai取成Aj
因为它们是相等的
都取成了一个变量A
因为Ai跟Aj相等
Aj的产物是w
Ai的产物也可以看出是w
因为Ai跟Aj是相等的
下面可以把这个Aj又取成原来的Ai
Ai的产物是vwx
这样得到一个新的产物
也就是说，我们通过Ai等于Aj
得到了这个语法分析树uwy
应该是S为根结点的产物
这u vv w xx y
也应该是这个语法分析树的产物
依此类推
我们就得到Chomsky范式
pumping的一个特性
就是对任何的i
u、v的i次方 w、x的i次方 y
都应该在这个语言里
这就是i等于0的情况
这就是i等于2的情形
这样就推出了无限的
上下无关语言的一个必要条件
只要是一个无限的上下无关语言
它必须满足这个特性
这节内容讲到这里
-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
-习题--作业
-期中考试
