问题标签 [pumping-lemma]

我对抽水引理相对较新，我在这里有一个问题，我认为我回答正确，谁能告诉我这是否有效，如果无效，为什么不

问题：{www | w 是 {a,b}*}

我的做法：

L = www

u* (v^k) * w 必须是 L 的子集

万维网

| | |

紫外线

紫外线 = 万维网

(u) (v^2) (w) = wwww

wwww 不是语言 www 的一部分，因此不是常规的

编辑：好吧，根据我的理解，抽引引理通过采用我们正在查看的“测试字符串”并将其拆分为一个保持相同的部分，然后是一个可重复的部分，最后是另一个保持不变的部分。在我的“方法”中，我将测试字符串“www”拆分为 u、v 和 w，每个分别持有一个“w”，其中 v 是可重复部分，另外两个是保持相同的部分。我将 v 部分加倍，最后得到一个结果 uvvw，它转换为 wwww，看起来好像它不是语言 www 的一部分。我有一种很好的感觉，我错了，因为我认为包括空字符串的条件“w is {a,b}*”，并且由于空字符串在 wwww 和 www 中是可行的，所以我的泵引理是错误的。

当一种语言满足常规语言的泵引理时，并不总是意味着它是一种常规语言。那么它至少是一种上下文无关的语言吗？或者介于两者之间？

1. 使用正则语言的抽引引理，证明

   语言 L = { a ⁱ , b ^j c ^k | i, j, k 是非负整数，并且 i=j 或 i=k }

不规则

2. 为上述语言设计 CFG

这就是我想出的

现在我必须将上面的 CFG 转换为我遇到问题的 chomsky 范式......有什么帮助吗？

有一个直接的证明方法：如果p是抽水长度，我们取字符串，那么无论分解是什么，字符串都将等于语言中不存在的字符串。s = 0p1p+p!s = xyzxy1+p!/|y|z0p+p!1p+p!

我不明白这里给出的 y 值。

所以我有一个家庭作业问题，要求证明 A = {a^nb^nc^n | n >= 0} 是非正则的，使用抽水引理。从我的教科书：

要使用泵引理证明语言 B 不是正则的，首先假设 B > 正则以获得矛盾。然后使用泵浦引理保证>存在一个泵浦长度p，使得B中所有长度为p或更大的字符串都可以被>泵浦。接下来，在 B 中找到一个具有 p 或更大但无法抽出的字符串 s。>最后，通过考虑将 s 划分为 x、>y 和 z 的所有方式来证明 s 不能被抽运（如果方便，请考虑抽运引理的条件 3），并且对于 >每个这样的划分，找到一个值 i，其中xy^iz 不在 B 中。这最后一步通常 > 涉及将各种将 s 划分为若干案例的方法进行分组并 > 逐个分析它们。

由此，以及我的教授在讲座中所说的话，在我看来，如果没有考虑 xyz 的不同分组的最后一步，条件 3 可以用来证明 B 是不规则的。也就是说，我不知道该怎么做。

对于我的证明，我认为 s = a^pb^pc^p 用于泵送长度 p。鉴于此，s 比泵送长度长，并且可以被泵送。抽水引理的第三个条件是 xy <= p 的长度。对于最明显的分组，其中 p 仅由 b 组成，y 的长度为 p，因此 xy 将违反条件 3，因为 x 也是长度 p。

但是，这就是我感到困惑的地方，在我看来，这并不能证明 s 无法抽水。仍然需要考虑 xyz 的不同分组，以表明不存在满足条件 3 的分组。

所以我明白为什么 A 不规则，我可以证明它。但在我看来，关于如何应用条件 3 来简化证明，我似乎遗漏了一些东西，并试图更全面地理解这一点。

我应该如何L={a^n b^m | n=km for k in N}使用抽水引理证明这不是常规语言？

我从输入一个词w开始L，w=a^n b^m用n=km一些k输入N。有三种可能的分解w：

1. a^i * a^j * a^(n-i-j) b^m
2. a^i * a^(n-i) b^j * b^(m-j)
3. a^n b^i * b^j * b^(m-i-j)

抽点 2) 的中间部分会导致混淆的词，这显然不是 in L，但我不明白为什么 1) 不能给你一个很好的分解：

假设你抽水a^j x时间。那么新单词中 a 的数量将是i+xj+n-i-j = n+(x-1)j。我们知道n=km一些m。我们必须证明存在一个x这样的新词不在L. 但是让我们假设j=m（这当然是可能的，因为n=km总是有足够数量的 a，除非当k=0，但是我们得到一个微不足道的情况）。然后n+(x-1)j = km+(x-1)m = m(n+x-1)which 是{a^n b^m | n=km for k in N}all的形式x。所以对于每一个w我们都有一个分解uvz，这样u v^i z就L适用于所有i。因此，由抽引理，L是正则的。

我错过了什么？

编辑：给出的泵送引理的公式：

让L成为带有k状态的 DFA 接受的常规语言。让w任何单词 in Lwith length >= k。然后w可以写成u v zwith |uv| <=k, v>0and u v^i zin Lfor alli>=0

对于语言 {a^2^n | n >= 0}

我知道首先选择了一些 k，然后 z = uvwxy 使得 vx != epsilon 和 #(vwx) <= k，但我想不出任何 i 可以证明这种语言不是上下文无关的。

证明 a^nb^n, n >= 0, 是非常规的。使用字符串 a^pb^p。

我见过的每个示例都声称 y 可以包含 a、b 或两者。但是我看不出 y 怎么能包含除 a 之外的任何东西，因为如果 y 包含任何 b，那么 xy 的长度必须大于 p，这使得它无效。

相反，例如：

www, w 是 {a, b}*，使用的字符串是 a^pba^pba^p b。在我看到的证明中，它声称 y 不能包含除 a 之外的任何东西，原因我在上面说。为什么这不一样？

还抛出另一个问题：

描述以下“证明”中的错误，即 0* 1* 不是常规语言。（必须存在错误，因为 0* 1* 是常规的。）证明是矛盾的。假设 0* 1* 是规则的。令 p 为 0* 1* 的泵送长度，由泵送引理给出。选择s为字符串OP P。你知道s是0*1*的成员，但是a^pb^p不能抽。这样你就有矛盾了。所以 0* 1* 是不规则的。

我找不到这个证明有什么问题。我只知道 0*1* 是正则语言，因为我可以构造一个 DFA。

My question concerns using the Pumping Lemma for Regular Languages to prove that the longest string in a finite language MUST be less than the number of states in a DFA recognizing the language. I was hoping to find an algebraic argument for this, but it seems the proof must rely on the Pigeonhole Principle. If p = the number of states in a DFA that recognizes the finite language, by the Pigeonhole Principle the longest string must be of size equal to p-1 (in other words, every pigeonhole must have a pigeon in it. Because the string is finite, there can be no pigeonhole with more than one pigeon in it).

If the length of the longest string in the finite language is less than p-1, the longest string is not guaranteed to reach an accept state. If the length is greater than p-1, the computation must "die" before the string is fully processed, thereby not being accepted by the DFA.

Is the above a valid argument for proving that the length of the longest string in a finite language must be less than or equal to the number of states?

我在一个相当困难的问题上遇到了一些麻烦。我被要求证明语言 {0^n 1^m 0^n | m,n >= 0} 使用抽水引理是不规则的。在我见过的所有例子中，语言只被提升到同一个变量（即a^nb^n）。所以我的问题是，如何选择合适的字符串来测试这种语言是否不规则？

对该问题的后续跟进是，一旦我有了我的字符串，你如何将字符串分解为 xyz where |xy| 的形式 <= 泵送长度和 |y| >=1？