我的问题是：
令 L = { x in {a,b}* | x 具有相同数量的 a 和 b}
我知道这是一种上下文无关语言，因为我可以为它创建一个语法（e 是 epsilon）：
S -> aX | bY | e
X -> bS | aXX
Y -> aS | bYY
您还可以通过使用与常规语言相交的上下文无关语言是上下文无关的事实来证明它是上下文无关的。
由于它是一种上下文无关语言，根据 CFL 的抽运引理，任何长于抽运长度 p 的字符串都应该能够被抽运。但是，如果我选择字符串 s = a^pb^pa^pb^p，则无法抽出该字符串，因此该语言不应该是上下文无关的。
我哪里错了？
当然可以抽绳子。让u = a^p b^(p-1), v = b, x = e, y = a, z=a^(p-1) b^p. 现在uvxyz = s，对于任何 iu v^i x y^i z都有相同数量的 as 和 bs。
让 u = a^p, v = b^(p-1), x = ba, y = a^(p-1), z = b^p，这样你的字符串 s = uvxyz。
那么 uv^ixy^iz 形式的任何字符串都在语言中，因此满足 CFL 泵引理的条件。
对于您的示例，泵送长度不是“p”……也许这就是您感到困惑的地方？
编辑： sepp2k 正确指出我对 vxy 的选择违反了 |vxy| 的条件。< = p，语言的抽水长度。他的解 v=b, x=e, y=a 是正确的。对于这种语言，任何长度为 2 或更大的字符串都会抽水——“ab”或“ba”必须出现在某处，因此 vy = ab 或 vy = ba 将始终有效。