解释上下文无关语言的泵引理
Pumpinglemmaforcontextfreelanguage(CFL)用于证明一种语言不是上下文无关语言
假设L是上下文无关语言
然后有一个泵浦长度n使得任何长度>=n的字符串wεL都可以写成如下-
|w|>=n
我们可以把w分成5个字符串，w=uvxyz，比如下面给出的
|vxy|>=n
|维|#ε
对于所有k>=0，字符串uvkxyyz∈L
通过使用泵引理证明语言不是上下文无关的步骤解释如下-
假设L是上下文无关的。
泵送长度为n。
所有长度超过n的字符串都可以抽|w|>=n。
现在在L中找到一个字符串'w'使得|w|>=n。
将w分成uvxyz
证明uvkxykz∉L对于某些k
然后，考虑将w划分为uvxyz的方式。
证明这些都不能同时满足所有3个泵送条件。
w不能被抽（矛盾）。
示例
找出L={xnynzn|n>=1}是否是上下文无关的
解决方案
让L是上下文无关的。
L必须满足泵送长度，例如n。
现在我们可以取一个字符串，使得s=xnynzn
我们将s分成5个字符串uvxyz。
令n=4所以s=x4y4z4
情况1：
v和y每个只包含一种类型的符号。
{我们只考虑v和y，因为v和y有功率uv2xy2z}
Xxxxyyyyzzz
=uvkxykz当k=2
=uv2xy2z
=xxxxxxyyyyzzzzz
=x6y4z5
(x的数量#y的数量#z的数量)
因此，结果字符串不满足条件
x6y4z5∉L
如果一种情况失败，则无需检查另一种情况。
案例2：
v或y有不止一种符号
xxxxyyyyzzzz
=uvkxykz(k=2)
=uv2xy2z
=xxxxyyxxyyyyyzzzz
=x4y2x2y5z2
这个字符串不遵循我们的字符串xnynzn的模式