正常语言的抽取引理

Question

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

假设我们必须检查是否:

L. 语言是否接受0常规或非常规的语言？

我们知道这是常规的,因为我们可以为L构建DFA.但我想用抽取引理来证明这一点.

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

现在,将分字符串x = 0,y = 0和z = 00.现在应用泵浦引理i = 2,我将得到字符串"00000",这是我的语言不存在所以通过引入引理证明语言不规则.但它被DFA接受了吗？

任何帮助将不胜感激,
谢谢

Answer 1

你并不完全清楚泵浦引理.

什么抽水引理说:

正式定义:常规语言的抽取引理

让我们L成为常用语言.然后存在一个整数仅取决于使得每个字符串中的至少长度的(被称为)可以写成= (即,可以被分为三个子串),满足以下条件:p ? 1LwLpp"pumping length"wxyzw

1. |y| ? 1
2. |xy| ? p
3. 为了所有人,i ? 0xyiz ? L

但这句话所说的是:

如果一种语言真的是一种常规语言,那么必须有一些方法从所有足够大的字符串生成(泵)新字符串.

1. 足够大的字符串是指,在语言中的字符串,它是长度≥的 P.
   _{因此,即使语言是常规语言,也可能无法从小字符串生成新字符串}

2. 某种方式意味着,如果语言真的是常规的,我们的选择w是正确的.然后应该至少有一种方法可以打破w三个部分,xyz这样通过重复(抽吸)y任意次,我们可以在语言中生成新的字符串.
   _{正确选择w:手段w在语言和足够大的≥ P}

注意:在第二点,可能有可能即使你按照正式定义w正确地打破了xyz一些新的生成字符串仍然没有语言. 就像你做的那样.

在这种情况下,你要重新尝试其他一些可能的选择y.

在你选择的字符串w=" 0000 "中你可以打破w这样的y = 00.通过这种选择,y您总能在语言中找到一个新的生成字符串,即"偶数个零"

_{一个错误,你正在做你证明你正在做一个特定的字符串0000.您应该证明所有w≥ P.所以你的证据仍然不完整}

在普通语言的抽水乳房的背景下阅读我的这个答案

在这个问题的答案,我已经解释过破w成xyz和抽水y手段寻找循环的一部分,并重复循环的一部分,以产生新的字符串的语言.
当我们证明某些语言是正常的; 那么实际上我们不知道循环部分在哪里,所以我们尝试所有可能的选择,满足抽取引理的规则1,2和3.

而Pumping引理说如果语言是规则的且无限的,那么DFA中必须有一个循环,并且语言中的每个足够大的字符串都会通过DFA的循环部分(根据鸽子原理)(因此y不能为空.这是规则-1在上面的正式定义中).

认为,环可以是在初始位置或结束等x和z可以为空字符串.

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

为了证明一种语言是常规的:你要证明对于语言中所有足够长的字符串(w),至少有一种方式(y)通过重复循环部分任意数量(i)次数来生成语言中的新字符串.

为了证明语言是不正规:你要找到至少一个足够长的字符串(w ^语言),使得对于没有选择任何方式"Y",使得其可能产生新的字符串与所有可能的重复(我).

To proof using Pumping Lemma: 
+-------------------------+--------------------------+----------------+--------------+
|                         | Sufficient large W in L  |     y          |    i >=0     |
+-------------------------+--------------------------+----------------+--------------+
| language is regular     | For all W (all W can use | At-least one   | For all i>=0 |  
|                         | to generate new W' in L) |                |              |
+-------------------------+--------------------------+----------------+--------------+
| language is NOT regular | Find Any W (at-least 1   | With all (Show | At-least one |   
|                         | W that can't generates   | no possible Y  | i            | 
|                         | new W' in L              | exists)        |              |
+-------------------------+--------------------------+----------------+--------------+

注意::规则始终不适用于"天气语言是否正常？"

抽取引理是必要的,但不足以使语言成为常规.满足这些条件的可能语言可能仍然是非常规的.
参考

为了证明一种语言是正常的,你有一些必要和充分的条件来使语言成为常规.