8 上下文无关语言和非上下文无关语言8.1 上下文无关语言的泵引理从第6章到第7章，我们给出了两种描述CFL的模型，CFG和PDA。

这两种模型都没有提供直接、明确的方法来判断一个形式语言不是CFL。

然而，正如例子6.7对自然语言的一个简单考察，我们发现CFG存在描述能力的局限。

本节中，我们精确定义和讨论CFL的一个性质，它类似于正则语言的泵引理。

利用这个性质能够发现许多不是CFL的语言。

正则语言的泵引理基于这样的事实，如果一个足够长的输入字符串x导致FA在状态转移中，到达某个状态超过一次，即接受路径上存在回路，根据回路容易将x分成三部分，u是回路之前的字符串，v是回路的字符串，w是回路后的字符串，那么在回路上的多次重复，得到的新的字符串也应该被FA接受，即对任意的m>=0，uv m w被FA接受。

如果我们用CFG生成（而不是PDA移动）CFL，容易得到类似的观察。

设CFG G的一个推导出现同一个非终结符的嵌套重复，如下面的形式，S⇒*vAz⇒*vwAyz⇒*vwxyz其中，v, w, x, y, z∈∑*。

推导过程中，出现了A⇒*wAy，我们可以多次重复这个推导过程，如S⇒*vAz⇒*vwAyz⇒*vw2Ay2z⇒*vw3Ay3z⇒*...⇒*vw m Ay m z又由于A⇒*x，因此所有这类字符串vxz, vwxyz, vw2xy2z, ..., vw m xy m z都输入语言L(G)。

为了将上面的观察总结成CFL的泵引理，我们必须说明对于足够长的字符串的推导过程中都会出现非终结符的嵌套重复。

同时我们也尽量发现分解得到的5个子串：v, w, x, y, z，的一些性质。

这类似于我们处理正则语言的泵引理。

在6.6节，我们证明了所有的CFG产生式都可以改写成Chomsky范式，而不会影响CFG 接受语言的能力（唯一的影响是不能接受空字符，由于此处仅仅关心足够长的字符串，因此这个影响可以忽略）。

因此我们的讨论可以局限在Chomsky范式（CNF）表示的CFG，显然这类文法得到的推导树都是二叉树，即每个父节点至多有两个子节点。

我们先定义几个与二叉树相关的概念。

路径是一串节点组成的序列，前后节点之间有父子关系；路径的长度是路径包含的节点的个数；二叉树的高度是最长路径的长度。

由于非终结符数目有限，如果推导树足够高，那么存在一个路径，某个非终结符在该路径上出现了两次，即出现了前面提到的嵌套重复现象。

引理8.1 任给h>=1，如果二叉树的叶结点个数>2h-1，那么该二叉树的高度>h。

证明：这是一个数学问题。

我们用数学归纳法证明它的逆反命题：如果二叉树的高度<=h，那么二叉树的叶节点个数<=2h-1。

1.归纳基础，h=1，此时二叉树只有一个根节点，它也是唯一的叶结点，命题成立。

2.归纳推理，设k>=1时，命题成立。

要证明k+1时，命题也成立。

设二叉树T的高度为k+1，则它的根节点的两个子树（以子节点为跟的二叉树）的叶节点数都<=2k-1，因此T的叶节点数<=2k-1+2k-1=2k。

得证。

定理8.1 G=(V, ∑, S, P)是形式为CNF的CFG，共有p个非终结符，则对每个长度>=2p+1的属于L(G)的字符串，都能找到5个字符串v, w, x, y, z满足下面的条件：u=vwxyz|wy|>0|wxy|<=2p+1vw m xy m z∈L(G), ∀m>=0证明：根据引理8.1，任何一个生成u的推导树高度>=p+2，即至少存在一个长度>=p+2的路径，不妨设d是其中的一个，显然d的最底部是一个终结符，其上的符号都是非终结符，共有p+1个，而不同的非终结符只有p个，根据鸽笼法则，至少存在一个非终结符A在路径d上出现了至少两次，分别将其中最接近根和最接近叶的标记为A1和A2，设A2生成的字符串是x，A1生成的字符串是wxy。

在wxy之前的字符串记为v，在wxy之后的字符串记为z。

图8-1直观地给出了这5个字符串在推导树上的位置。

由于A1为根的推导树高度<=p+2，因此|wxy|<=2p+1。

由于A1为根的推导树是二叉树，因此出了存在从A1到A2的路径，还存在其他路径，则|wy|>0。

最后，存在如下的嵌套重复，S⇒*vAz⇒*vwAyz⇒*vwxyz因此满足第4个条件。

类似有限自动机的泵引理，我们也给出一系列CFG的泵引理。

定理8.1a （CFL的泵引理）语言L是CFL，则存在一个整数n，使得对每个u∈L，|u|>=n，都存在5个字符串v, w, x, y, z，满足下面的条件，u=vwxyz (8.1)|wy|>0 (8.2)|wxy|<=n (8.3)vw m xy m z∈L(G), ∀m>=0 (8.4)证明：L是CFL，则存在一个CNF形式的CFG生成L-{Λ}，它的非终结符个数是p，则令n=2p+1，根据定理8.1直接得到定理8.1a的结论。

类似FA的泵引理（见第5章），本节的泵引理也常常用来证明某个语言不是CFL。

通常采用反证法，即要证明对任给的整数n，都存在一个u∈L，|u|>n，找不到满足上面4个条件的5个字符串。

还有另外的方法说明一个语言不是CFL。

根据第7章，由一个FA加一个辅助存储空间（栈）组成的PDA能够接受一个CFL，如果我们能够说明接受一个语言的抽象机至少需要两个栈，那么就能说明这个语言不是CFL。

比如我们知道接受语言a i b i的抽象机只需要一个栈，即用一个栈记住前面的a的个数，然后与后面的b比较。

那么容易想到，仅仅一个栈不能接受语言a i b i c i。

下面我们用泵引理来证明我们的直观判断。

例子8.1 语言L={a i b i c i | i>=1}，证明L不是CFL。

分析：反证法。

假设L是CFL，则存在定理8.1a定义的n，选择u=a n b n c n，显然|u|>n，设存在5个字符串v, w, x, y, z满足式子(8.1)-(8.4)。

由于|wxy|<=n，因此w, x和y至多包含两种字符，又因为|wy|>0，因此无法满足式子vw m xy m z∈L(G), ∀m>=0，得到矛盾，得证。

显然这个方法实际上证明了更大的语言L1={u∈{a, b, c}* | n a(u)=n b(u)=n c(u)}是非CFL（选取同样的u）。

例子8.2 语言L={ss | s∈{a, b}*}是非CFL。

分析：前面我们讨论了语言{ss r | s∈{a, b}*}是CFL。

例子8.1揭示了一个栈不够用的情况，这个例子则显示了数据结构栈不合适的情况。

显然，如果PDA用到的辅助空间不是栈，而是队列，那么就能够类似接受回文语言那样接受L。

反证法，设L是CFL，则存在n，选择u(n)=a n b n a n b n，设存在v, w, x, y, z满足式子(8.1)-(8.4)，我们来发现其中的矛盾。

类似例子8.1，由于|wxy|<=n，则wxy至多包含上面4组字符串的两组，我们分情况讨论。

1. wxy包含第1组和第2组，则vw0xy0z=a i b j a n b n, i<n, j<n，显然vw0xy0z∉L，矛盾；2. wxy包含第2组和第3组，则vw0xy0z=a n b i a j b n, i<n, j<n，显然vw0xy0z∉L，矛盾；3. wxy包含第3组合第4组，则vw0xy0z=a n b n a i b j, i<n, j<n，显然vw0xy0z∉L，矛盾；其他情况可类似证明。

类似例子8.1，例子8.2可用于证明其他一些语言不是CFL ，比如{a i b i a i b i | i>=0}, {a i b j a i b j | i,j>=0}, {scs | s ∈{a, b}*, c 是特殊字符}等。

上面证明中如何选择u 成为关键，尽管正确的选择可能不止一个，但大多数选择不能导出矛盾。

一旦u 选好后，则往往需要分情况讨论。

比如例子8.2，可以分下面7种情况讨论，1. wy 只包含第一组的a2. wy 包含第一组的a 和第二组的b3. wy 只包含第二组的b4. wy 包含第二组的b 和第三组的a5. wy 只包含第三组的a6. wy 包含第三组的a 和第四组的b7. wy 只包含第四组的b这些情况的讨论中，常常有相似之处，可以互相借用。

最后要选择m 的值来导致矛盾，通常有多种值可选择，不过用得最多的是m=0或m=2。

例子8.3 语言L={x ∈{a, b, c}* | n a (x)<n b (x) and n a (x)<n c (x)}不是CFL 。

分析：这个例子与例子8.1很像，PDA 只有一个栈，可以用来比较a 和b 的数目，也可以用来比较a 和c 的数目，但不能同时完成两个比较，因此问题源于栈数目不够。

反证法，设L 是CFL ，则存在n ，令u=a n b n+1c n+1，设存在满足式子(8.1)-(8.4)的v, w, x, y, z 。

分两种情况讨论：1. wy 中至少含有一个a ，则wy 不能含有c ，因此vw 2xy 2z ∉L ；2. wy 中不含a ，则vw 0xy 0z ∉L 。

两种情况都导致矛盾，得证。

注意，上面的方法还可用于说明语言{a i b j c k | i<j and i<k}不是CFL 。

例子8.4 在5.5节我们说明了程序设计语言C 存在不能成为正则语言的特征，在第6章，我们用CFG 描述了高级程序设计语言的部分语法，本例我们将说明整个高级程序设计语言，比如C ，不是CFL 。

分析：C 语言的一个特点是，变量在使用之前必须先声明，这个规则等同于规定字符串具有这样的形式，xcx 。

其中，x 是标识符，c 是两个标识符之间的字符串。

例子8.2已经说明了语言{xcx | x ∈{a, b}*}不是CFL ，本例扩大了x 的字母表，c 变成了字符串，但问题的实质没有改变。

反证法，设L 是CFL ，则存在n 。

选择⎭⎬⎫⎩⎨⎧=;...;...;...int ()321321321n n n a aa a aa a aa main uu 中只有一个空格在int 之后，这个句子可能带来编译器的警告，但能够通过编译器并得到可执行程序，即先声明了aa...a ，然后两次使用aa...a 。

根据泵引理，存在u=vwxyz ，|wxy|<=n ，分情况讨论xy ：1. wy 包含空格，则vw 0xy 0z 不再是合法的C 程序；2. wy 不包含空格，wxy 只在第一组aa...a ，则vw 0xy 0z 将改变生命，后面引用非法，不是合格的C 程序；3. 类似讨论其他情况，vw 0xy 0z 都不再是合法C 程序。