math - 使用上下文无关语言抽取引理

Question

我有{a^i b^j c^k | i,j,k>=0 & i>j & j>k} 我开始假设m为我挑选一些的语言，例如一个字符串

   z = a^m b^(m-1) c^(m-2)

然后将字符串拆分为不为空的字符串，(z =) uvwxy然后 当我选择一个“ ”时，我感到困惑。假设我选择然后我有： 而且我不完全确定从哪里开始，因为对我来说，看起来我可以选择该语言中的 vwx。vx#(vwx)<=mii=1uv^1wx^1y

有什么建议么？

Answer 1

我首先选择一个稍微好一点的 z = a^(m+2)b^(m+1)c^(m)，其中 m 是泵送长度。这个字符串显然是语言，它的长度大于或等于m。因此，假设该语言是 CFL，则泵引理适用于它。现在，既然你知道 |vwx| <= m 并且 |vx| > 0，你也知道 vwx 必须由 (1) 只有 a，(2) 一些 a 和一些 b，(3) 只有 b，(4) 一些 b 和一些 c，或 (5) 只有 c。

分别处理每个案例。我会为你做前两个案例。

情况 1：这意味着对于某些 s > 0，vx 是 a^(s)，因为引理告诉我们 |vx| > 0。现在假设你取 i = 0。那么引理告诉我们 z' = uv^(0)wx^(0)y 应该仍然属于该语言。然而，z' 的形式为 a^(m+2-s)b^(m+1)c^(m)，并且由于 s > 0，违反了 a 的数量必须严格大于b 的数量。因此 z' 不在该语言中，并且这种情况无法抽出。

情况 2：这意味着对于某些 s,t，vx 是 a^(s)b^(t)，使得 s+t > 0。再次假设您取 i = 0。那么 z' 的形式为 a^ (m+2-s)b^(m+1-t)c^(m)。如果 t 为正，则违反 b 的数量严格大于 c 的数量的条件。如果 t 为零，则 s 必须是正数，在这种情况下，我们会退化为情况 1。因此 z' 不在语言中，并且这种情况无法抽出。

对于其他情况，请记住您可以为每种情况选择不同的泵送指数 i。

编辑：（根据过去对这个问题的讨论，我决定展示其他三个案例。）

情况 3：这意味着对于某些 s > 0，vx 是 b^(s)。取 i = 0。那么 z' 的形式为 a^(m+2)b^(m+1-s)c^(米）。由于 s 是正数，这违反了 b 的数量严格大于 c 的数量的条件。所以 z' 不在语言中，这种情况下无法抽水。（您也可以将 i 设为除 1 以外的任何值，以表明这种情况无法抽水。）

情况 4：这意味着对于某些 s,t，vx 是 b^(s)c^(t)，使得 s+t > 0。取 i = 2。然后 z' 的形式为 a^(m+2) b^(m+1+s)c^(m+t)。如果 s 不为零，则违反了 a 的数量严格大于 b 的数量的条件。如果 s 为零，则 t 必须为非零，在这种情况下，违反了 b 的数量严格大于 c 的数量的条件。所以 z' 不在语言中，这种情况也无法抽水。

情况 5：这意味着对于某些 s > 0，vx 是 c^(s)。取 i = 2。然后 z' 的形式为 a^(m+2)b^(m+1)c^(m+ s)。由于 s 为正数，因此违反了 b 的数量严格大于 c 的数量的条件。所以 z' 不在语言中，这种情况下无法抽水。

由于所有五个案例都无法抽出，抽水引理告诉我们这种语言不是上下文无关的。

Answer 2

注意：在评论中反复讨论之后，我发现我错了，威廉的回答实际上是正确的。我将把这个答案留在这里，以便指出我的推理失败的地方。

我会这样想：

子串 v,w,x 必须具有哪些属性才能在泵送后甚至有机会保留在语言定义中？v 和 x 都不能包含像“ab”或“bc”这样的子字符串，否则它们会立即从输入语言中抽出。因此，v 和 x 中的每一个都必须为空、全为 a、全为 b 或全为 c。

考虑语言中的字符串 aaabbc。

现在如果我们选择 u="aa", v = "a", w = epsilon, x = "b", y = "bc" 会发生什么；和泵 v 和 x？（这是我的错误：我没有考虑 n=0 的情况，其中 v 和 x 实际上已从字符串中删除；无论您如何选择 uvwxy，对于 n=0 或 n>1 的情况，当uvwxy 被抽到 uv ⁿ wx ⁿ y)。

注意：CFL 泵引理可用于证明一种语言不是上下文无关的，但遵守泵引理本身并不足以证明语言 是上下文无关的。有些语言不是 CF，但 CFL 泵引理的所有条件仍然成立。对于这种情况，您可能需要查看Ogden 引理，这是一种更强大的测试，看看是否可以用来证明您的语言不是 CF。

Answer 3

抽水引理说，如果一种语言是上下文无关的，那么它就会“抽水”。也就是说，如果它是上下文无关的，那么：

有一些最小长度 p，因此任何长度为 p 或更长的字符串 s 都可以重写为 s=uvxyz，其中 u 和 y 项可以在原地重复任意次数（包括零次）。

一个典型的用途是证明一种语言不会抽水，以证明它不是上下文无关的。从您的工作看来，这就是您正在尝试做的事情。

But the converse of the pumping lemma is false: There are languages which pump but are not context-free. In fact, your language is just such a beast. In other words, your language is not context free, but it does pump. (The easiest way to prove this is split s so that v="a" and y="b".) Therefore the pumping lemma is not likely to be useful to you in the analysis of this language. You may wish to consider Ogden's lemma instead.