解释上下文无关语言的泵引理

Pumping lemma for context free language (CFL) 用于证明一种语言不是上下文无关语言

假设 L 是上下文无关语言

然后有一个泵浦长度 n 使得任何长度 >=n 的字符串 w εL 都可以写成如下 -

|w|>=n

我们可以把w分成5个字符串，w=uvxyz，比如下面给出的

• |vxy| >=n

• |维| #ε

• 对于所有 k>=0，字符串 uv ^k xy ^y z∈L

通过使用泵引理证明语言不是上下文无关的步骤解释如下 -

• 假设 L 是上下文无关的。

• 泵送长度为 n。

• 所有长度超过 n 的字符串都可以抽 |w|>=n。

• 现在在 L 中找到一个字符串 'w' 使得 |w|>=n。

• 将 w 分成 uvxyz

• 证明 uv ^k xy ^k z ∉L 对于某些 k

• 然后，考虑将 w 划分为 uvxyz 的方式。

• 证明这些都不能同时满足所有 3 个泵送条件。

• w 不能被抽（矛盾）。

示例

找出 L={x ⁿ yn ^z n|n>=1} 是否是上下文无关的

解决方案

• 让 L 是上下文无关的。

• L 必须满足泵送长度，例如 n。

• 现在我们可以取一个字符串，使得 s=x ⁿ y ⁿ z ⁿ

• 我们将 s 分成 5 个字符串 uvxyz。

令 n=4 所以 s=x ⁴ y ⁴ z ⁴

情况1：

v 和 y 每个只包含一种类型的符号。

{我们只考虑 v 和 y，因为 v 和 y 有功率 uv ² xy ² z}

X xx x yyyyz z z

=uv ^k xy ^k z 当 k=2

=uv ² xy ² z

=xxxxxxyyyyzzzzz

=x ⁶ y ⁴ z ⁵

(x的数量#y的数量#z的数量)

因此，结果字符串不满足条件

x ⁶ y ⁴ z ⁵ ∉ L

如果一种情况失败，则无需检查另一种情况。

案例2：

v 或 y 有不止一种符号

xx xx yy yy zzzz

=uv ^k xy ^k z (k=2)

=uv ² xy ² z

=xxxxyyxxyyyyyzzzz

=x ⁴ y ² x ² y ⁵ z ²

这个字符串不遵循我们的字符串 x ⁿ y ⁿ z ^{n 的模式}