我正在写一些关于 Ppumping Lemma 的东西。我知道语言 L = { a^nb^n| n ≥ 0 } 是上下文无关的。但我不明白这种语言如何满足抽引引理的条件（对于无上下文语言）？

如果我们选择字符串 s = a^pb^p, |s| > p , |vxy| < p 和 |vy| > 0。

当我们泵送它（泵升或降压）或者我缺少某些东西时，它似乎会超出语言范围。

任何解释都会有所帮助。

编辑：我将抽引引理应用于 a^nb^n 并且它无法在所有情况下都保持在语言中。那么，为什么它是无上下文的？

我只是想看看这种语言是否满足抽水引理的条件。但是当我抽水时它似乎失败了 s = uv^2xy^2z

虽然这个表达式被确定性有限自动化所接受，但是如果我们在这个表达式上应用抽引引理，抽引引理会失败，这个表达式也有有限状态但不会停止并连续运行，边缘会继续产生自循环 b/w当 i 趋于变大并且趋于无穷大时，它不应该停止。因此，对于这个表达式，可以绘制 DFA，但抽取引理和 TM 失败。那么，告诉这是否是常规语法？

I am a bit confused on the theory of the pumping lemma. As I know is used to decide if a language is regular or not. There is a variable let be m such that is the states?

So i cant understand how this is working. I mean where is that useful? By breaking a string into 3 parts and repeat the x? And how is that showing if it is regular or not? And is any difference between pumping lemma for regular languages and context-free languages?

我一直在 YouTube 上观看 Coderisland 关于有限状态机、DFA 和 NFA 的讲座，在一次讨论中，他谈到了如何使用抽水引理来展示一种语言是如何不规则的。我不太清楚如何应用引理，并想了解我是否做得对。如果我有类似的东西：

w = {a ⁿ b ^k , n =/= k}

我是否正确，我可以这样说：

h = {a ⁿ b ^{n + r} , r > 0} 是w的子集，因此如果我通过引理证明h不规则，那么w一定不是规则的，因为h是w的子集。

我要展示的方式如下：

1. h = xyz
2. |xy| <= n
3. x = ^n-r
4. y = a ^r
5. z = b ^{n + r}
6. xyz = a ^n-r a ^r b ^{n + r}
7. xy ² z = a ^n-r a ^2r b ^{n + r} = a ^{n + r} b ^{n + r}

因此h不可能是正则的，因为 a ^{n + r} b ^{n + r}不是 {a ⁿ b ^{n + r} , r > 0} 的形式，并且由于h不是正则w一定不是正则的，因为h是w。

我是否正确应用了它？我了解如何将它应用于像 {an b ^{n }}这样的简单语言，因为我可以将引理直接应用于这种语言，但我能想到的语言的唯一方法是创建一个属于我的语言的子集, 并将引理应用于此。

如果我没有正确应用它，有没有办法表明我的语言不规则（或规则），使用另一个引理，或者可能具有闭包属性？

这是一个非常棒的话题，即使我不完全理解抽水引理，我也很高兴能进一步探索它！

我试图展示抽水引理如何适用于肯定是常规的语言。我有超过 {0, 1} 的语言，它有偶数个 1。这种语言可以由具有两种状态的 DFA 表示。

所以这里的泵送长度是2，对吗？抽水引理指出“如果 s 是A 中长度至少为 p 的任何字符串”，那么它可以被划分为 xyz，使得 3 个 PL 条件为真。假设我们选择了一个字符串 '000110' 并想证明它可以以某种方式拆分成 xyz 使得 |xy| <= p（并且 |y| > 0，并且 x(y^i)z 在 L 中）。

在这种情况下，y 必须是“11”，这样它才能被重复并且仍然是偶数......这将使 x = '000'，对吗？这将使 |xy| = 5，大于 p。

我没有看到任何其他分割给定字符串的方法，以便 |xy| < 页。我在这里想念什么？非常感谢。

我想我知道抽水引理，并被告知 Myhill-Nerode 是一种非常优雅的方式来表明某事物是规则的还是不规则的。但我遇到了很多麻烦。以此为例：

= {0 ^k , k = 2 ⁿ , n >̲ 1}

我的语言是从 0 到 2 的幂的长度的重复。我想使用 Myhill-Nerode 来表明这是规则的还是不规则的。可能吗？

我知道如何将其设置为类似于其他 Myhill-Nerode 外观证明，但我不太了解等效概念。

我可以说我有一些和where ≠并且两者都是 2 ^h和的形式，然后我定义，这样：

= 0 ^j/2

= 0 ^p/2

= 0 ^j/2

其中= 0 ^j/2 0 ^j/2 = 0 ^j是我的语言，因为它的形式是 2 ⁿ，但是 = 0 ^p/2 0 ^j/2不能保证每个 p 和 j 都是我的语言，因为≠

1. 对于每个i ≥ 0,uv^ixy^iz ∈ A,
2. |vy| > 0， 和
3. |vxy| ≤ p.

对于 2，如果我们抽空 uvxyz，我们会得到 uxz，但它会违反 2。因为 |vy| = 0。

我在很多地方都看到了这个例子，我在哪里理解错了？

假设： L={a ⁿ b ^m c ^o | n < m < o, n natural}
使用抽水引理我选择了： z = uvwxy = a ⁿ b ⁿ⁺¹ c ⁿ⁺²
|uv|<=n 和 |v|>0
=> uv ² wx ² y
If vwx 属于 a 和/或 b 没关系，我们将拥有比 c 更多的 a 和/或 b - 但如果 vwx 仅包含 c，它将是 L 的元素。
据我所知，所有新词都必须不是元素L 以表明它不是 CFL。我该怎么做？

我一直在做一些课本上的问题来练习期末考试，但我遇到了一个我无法弄清楚的问题。基本上是为了

令 L = {w | w 包含的 0 多于 1 }

它暗示常规语言的引理应该有所帮助。

虽然当存在某种模式时很容易证明语言非常规，例如 0 的第一个后跟 1 或回文，因为您可以通过抽水来打破模式，但这里唯一的要求是单词，它可以包含 0 和 1任何顺序，都有更多的 0。

我试图考虑一些情况，最明显的情况是如果 y=0，你可以抽 y 直到你的 0 多于 1。但是我们必须考虑所有可能的情况，以证明泵引理是错误的，并且看起来 y 可以是任何字符串，只要 |xy| < p（其中 p 是泵送长度）。y 可以包含 0 和 1，或仅包含 1。我在这里遗漏了一些明显的东西吗？提前谢谢。

查找具有偶数个零的字符串是否为 a) 上下文无关 b) 常规

a) 使用 CFL 的泵引理....它可以表示为 e(0 ⁿ )e(0 ⁿ )e。所以，它是一个节能灯。

b）它可以用(00)*正则表达式表示。所以，我认为这是一种常规语言。但是，我无法使用常规语言的抽引引理证明相同

任何帮助将非常感激。谢谢！！