常规语言的抽引理

我在使用泵引理检查给定语言是否规则时有点困惑。

假设我们必须检查是否：

L.接受偶数的语言0是否正常？

我们知道它是正则的，因为我们可以为 L 构造一个 DFA。但我想用泵引理来证明这一点。

现在假设我拿一个字符串w= "0000":

现在将字符串划分为x = 0, y = 0, and z = 00。现在应用泵送引理i = 2，我会得到字符串"00000"，即not存在于我的语言中，因此通过抽引理证明该语言是不规则的。但DFA接受吗？

任何帮助将不胜感激
谢谢

您对泵引理并不完全清楚。

泵引理说了什么：

正式定义：常规语言的泵送引理 http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Formal_statement

Let L成为常规语言。那么存在一个整数p ≥ 1仅取决于L这样每个字符串w in L至少长度p (p被称为"pumping length"）可以写成w = xyz (i.e., w可以分为三个子串），满足以下条件：

1. |y| ≥ 1
2. |xy| ≤ p
3. for all i ≥ 0, xyiz ∈ L

但这个声明说的是：

如果一种语言确实是常规语言，那么一定有some way生成（pump) 新字符串来自all 足够大的字符串.

1. Sufficiently large string means, a string in language that is of the length ≥ P.
   _{So it may not be possible to generate new string from small strings even if language is Regular Language}

2. Some way means, if language is really a regular and our choice of w is correct. Then there should be at lest one way to break w in three parts xyz such that by repeating(pumping) y for any number of times we can generate new strings in the language.
   _{correct choice of w means: w in language and sufficiently large ≥ P}

note：在第二点中，即使你打破了，也有可能w正确进入xyz根据正式定义，仍然有一些新生成的字符串不是语言中的。正如你所做的那样.

在这种情况下，您将重试其他一些可能的选择y.

在你选择的字符串中w = "0000“你可以打破w这样y = 00。而有了这样的选择y您总是会在语言中找到一个新生成的字符串，即“偶数个零”

_{One mistake you are doing in your proof that you are doing for a specific string 0000. You should proof for all w ≥ P. So still your proof is incomplete}

阅读我的这个答案在常规语言的抽取引理的背景下 https://stackoverflow.com/questions/11832371/to-make-sure-pumping-lemma-for-infinite-regular-languages-only/13539823#13539823

在那个答案中，我已经解释过打破w into xyz和泵送y means 查找循环部分并重复循环部分以生成新字符串在语言中。
当我们证明某种语言是正规的；那么实际上我们不知道循环部分在哪里，因此我们尝试满足泵引理规则 1,2 和 3 的所有可能选择。

泵引理说，如果语言是规则的且无限的，那么 DFA 中一定有一个循环，并且语言中每个足够大的字符串都经过循环部分（根据鸽巢原理 http://en.wikipedia.org/wiki/Pigeonhole_principle）的 DFA（因此y不能为空。这是上面正式定义中的规则 1）。

想想，循环可以在初始位置或结束位置等等x and z可以是空字符串。

但实际上我们不知道循环在 DFA 中落在哪里，所以我们尝试了所有可能的方法。

证明一种语言是正规的: 你要证明这一点all足够长的字符串