需要澄清上下文无关语言的泵引理

Question

我正在做一个问题，我将泵引理应用于 CFL L = {a^nb^nc^n : n >= 0}。这是我正在查看的证明的开始：

1. 假设 L 是 CFL，因此 L 存在泵浦长度 p
2. 选择 w = a^p b^p c^p
3. 查看 uv^ixy^iz 的分解，其中： A。 |维| >= 1 b. |vxy| <= p

证据表明只有这些情况需要考虑，其他情况都没有必要考虑：

情况 1-3：v & y 仅包含 as 或 v & y 仅包含 bs OR v & y 仅包含 cs 情况 4-5：v & y 仅包含 as 和 bs 或 v & y 仅包含 bs 和 cs

为什么只有这些案例？为什么 v & y 不能包含 as 和 cs，或者 v & y 不能包含 as、bs 和 cs（例如 v 包含 as 和 bs，y 包含 bs 和 cs）。我看到解决方案的人解释说，因为我们使字符串的每个部分都有长度 p，所以尝试让 v 和 y 包含 as、bs 和 cs 将超过泵送长度 p，但我不明白它是如何实现的将超过泵送长度。他也没有解释为什么我们不能在 v & y 中使用 as 和 cs。如果有人能解释为什么在 v & y 中尝试使用 as、bs 和 cs 不起作用，以及为什么我们不能仅在 v & y 中使用 as & cs，我将非常感激。谢谢！

Answer 1

结构

在这种情况下，我们考虑的字符串结构是：

w = uvxyz = a^(p) b^(p) c^(p)

其中变量

p

表示泵送长度。

请注意，

w

的长度是泵浦长度的三倍。

冗余案例

vxy

包含

a^k b^l c^m

假设

vxy

包含符号“a”、“b”和“c”。 那么我们可以把这个结构写成：

• vxy = a^k b^l c^m

  这样

  k + l + m <= p

  ，由于抽引理规则 (

  |vxy| <= p

  )。

但是，由于原始字符串有 p a、p b 和 p c。我们知道在最后一个“a”和第一个“c”之间有p“b”。 这表明

l = p

。

鉴于：

k + l + m <= p

，我们现在通过用

l

代替

p

知道：

k + p + m <= p

，即

k + m <= 0

。 这表明如果这种情况是可能的，那么

k = 0

和

l = 0

。

这与我们的假设相矛盾，即该案例包含符号“a”、“b”、“c”，因为

k

和

l

或两者都为零，因此不存在“a”或“c”符号。 表明这种情况是不可能的。

vxy

包含

a^k c^l

如果一个字符串同时包含“a”和“c”，那么它之间还必须包含“b”符号，就好像它包含“a”一样，它必须通过“b”符号才能到达第一个“c” '.

因此，这种情况相当于先前不存在的情况。