pumping-lemma - 抽引理证明语言不规则

Question

嗨，我正在尝试为抽引引理做练习题。我需要证明语言 L = {w E 字母 a,b,c | w 中 bs 的数量是 cs 的两倍，bs 的数量是 cs 的两倍}

现在我创建了一个属于 L 的单词 w = a^4n * b^2n * c^n。我一直试图在计算中走得更远，但我不明白该怎么做。我如何找到 xyz 代表什么？我如何证明存在矛盾？我已经尝试了很长时间并且在互联网上到处寻找，但我真的很挣扎。

Answer 1

这是上下文无关语言的引理：

如果语言 L 是上下文无关的，则存在某个整数 p ≥ 1（称为“泵送长度”），使得wL 中每个长度为 p 或更多符号（即 |w| ≥ p）的字符串都可以写成

w = uvxyz，带有子串 u、v、x、y 和 z，这样

1. |vxy| ≤ p,
2. |维| ≥ 1，并且
3. 对于所有 i ≥ 0，u(v^i)x(y^i)z 在 L 中。

取自维基百科

我们来看看字符串w=(a^4p)(b^2p)(c^p)

为了证明矛盾，我们应该证明对于 的每个子串w，抽出这个词，将把它从语言中取出。

我们来看几个案例：

1. vxy（或者在您的情况下将其标记为“xyz”）包含1个字母的序列（假设字母是a这样的序列是a^k，其中k> = 1）。对于这种情况，例如，如果您为 i=2 抽取字符串，您将得到： u(v^2)x(y^2)z=uvvxyyz=(a^(4p+|vy|))(b^2p) (c^p) 这不是语言中的一个词，因为 4p+|vy| 大于 2*2p ( as 是 s 的两倍b)。

2. vxy 包含 2 个字母的序列（假设字母是as 后跟bs，所以序列是 (a^k)(b^l) k,l >= 1）。对于这种情况，如果你为 i=2 抽取字符串，你将得到： u(v^2)x(y^2)z=uvvxyyz=(a^(4p+|vy|))(b^(2p+|vy |))(c^p) 这不是语言中的一个词，因为 2p+|vy| 大于 2*p ( bs 是 s 的两倍c)

你可以证明，对于每个字母a，b或者c用第一个大小写抽出的单词会脱离语言，而对于每个 2 个字母的序列，(a^k)(b^l)或者(b^k)(c^l)用第二个大小写的抽出，都会使这个词脱离语言。

因为 |vxy| 的条件 ≤ p，我们不能得到 3 个字母的序列。我们可以用 3 个字母得到的最短子串是：a(b^2p)c，长度为 2p+2，这对这种情况无效。

因此，我们展示了对于我们选择的每个子字符串，抽出单词会将其从语言中取出。我们得到了一个矛盾，即这种语言符合抽水引理，因此这种语言不是上下文无关语言。