文档介绍：上下文无关语言的泵引理从第6章到第7章,我们给出了两种描述CFL的模型,CFG和PDA。这两种模型都没有提供直接、明确的方法来判断一个形式语言不是CFL。然而,,我们发现CFG存在描述能力的局限。本节中,我们精确定义和讨论CFL的一个性质,它类似于正则语言的泵引理。利用这个性质能够发现许多不是CFL的语言。正则语言的泵引理基于这样的事实,如果一个足够长的输入字符串x导致FA在状态转移中,到达某个状态超过一次,即接受路径上存在回路,根据回路容易将x分成三部分,u是回路之前的字符串,v是回路的字符串,w是回路后的字符串,那么在回路上的多次重复,得到的新的字符串也应该被FA接受,即对任意的m>=0,uvmw被FA接受。如果我们用CFG生成(而不是PDA移动)CFL,容易得到类似的观察。设CFGG的一个推导出现同一个非终结符的嵌套重复,如下面的形式,SÞ*vAzÞ*vwAyzÞ*vwxyz其中,v,w,x,y,zÎå*。推导过程中,出现了AÞ*wAy,我们可以多次重复这个推导过程,如SÞ*vAzÞ*vwAyzÞ*vw2Ay2zÞ*vw3Ay3zÞ*...Þ*vwmAymz又由于AÞ*x,因此所有这类字符串vxz,vwxyz,vw2xy2z,...,vwmxymz都输入语言L(G)。为了将上面的观察总结成CFL的泵引理,我们必须说明对于足够长的字符串的推导过程中都会出现非终结符的嵌套重复。同时我们也尽量发现分解得到的5个子串:v,w,x,y,z,的一些性质。这类似于我们处理正则语言的泵引理。,我们证明了所有的CFG产生式都可以改写成Chomsky范式,而不会影响CFG接受语言的能力(唯一的影响是不能接受空字符,由于此处仅仅关心足够长的字符串,因此这个影响可以忽略)。F)表示的CFG,显然这类文法得到的推导树都是二叉树,即每个父节点至多有两个子节点。我们先定义几个与二叉树相关的概念。路径是一串节点组成的序列,前后节点之间有父子关系;路径的长度是路径包含的节点的个数;二叉树的高度是最长路径的长度。由于非终结符数目有限,如果推导树足够高,那么存在一个路径,某个非终结符在该路径上出现了两次,即出现了前面提到的嵌套重复现象。>=1,如果二叉树的叶结点个数>2h-1,那么该二叉树的高度>h。证明:这是一个数学问题。我们用数学归纳法证明它的逆反命题:如果二叉树的高度<=h,那么二叉树的叶节点个数<=2h-1。归纳基础,h=1,此时二叉树只有一个根节点,它也是唯一的叶结点,命题成立。归纳推理,设k>=1时,命题成立。要证明k+1时,命题也成立。设二叉树T的高度为k+1,则它的根节点的两个子树(以子节点为跟的二叉树)的叶节点数都<=2k-1,因此T的叶节点数<=2k-1+2k-1=2k。得证。=(V,å,S,P)F的CFG,共有p个非终结符,则对每个长度>=2p+1的属于L(G)的字符串,都能找到5个字符串v,w,x,y,z满足下面的条件:u=vwxyz|wy|>0|wxy|<=2p+1vwmxymzÎL(G),"m>=0证明:,任何一个生成u的推导树高度>=p+2,即至少存在一个长度>=p+2的路径,不妨设d是其中的一个,显然d的最底部是一个终结符,其上的符号都是非终结符,共有p+1个,