regular-language - 常规语言的抽动引理

Question

在检查给定语言是否正常时，我有点困惑。

假设我们必须检查是否:

L. The language accepting even number of 0's in regular or not?

我们知道这是常规的，因为我们可以为L构造DFA。但是我想用抽引引理证明这一点。

现在假设，我采用String w= "0000":

现在将字符串分为 x = 0， y = 0和 z = 00。现在，在为 i = 2应用泵送引理时，我将获得字符串 "00000"，该字符串在我的语言中不存在，因此通过泵送引理可以证明该语言不规则。但这是DFA接受的吗？

任何帮助将不胜感激
谢谢

Answer 1

您对抽引引理还不是很清楚。

抽引引理说:

正式定义:Pumping lemma for regular languages

Let L be a regular language. Then there exists an integer p ≥ 1 depending only on L such that every string w in L of length at least p (p is called the "pumping length") can be written as w = xyz (i.e., w can be divided into three substrings), satisfying the following conditions:

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

但是，该语句的意思是:

如果一种语言确实是一种普通语言，那么必须有某种方法可以从 所有足够大的字符串生成(抽出)新字符串。

足够大的字符串表示长度大于等于P的语言字符串。
因此，即使语言是常规语言

，也 可能无法从 小字符串生成新字符串

某种程度上，表示，如果语言确实是一种常规并且我们对w的选择是正确的。然后，至少应该有一种方法可以将w分为三部分xyz，以便通过重复(抽取)y任意次数，我们可以生成该语言的新字符串。
正确选择w的意思是:语言中的w且足够大≥P

注意:在第二点上，即使您根据正式定义将 w正确地分割为 xyz，也有可能会出现一些新生成的字符串不在语言中的情况。和你一样

在这种情况下，您将尝试使用 y其他可能的选择。

在您选择的字符串 w =“ 0000 ”中，您可以将 w破坏为 y = 00。通过选择 y，您将始终在Language中找到一个新生成的字符串，该字符串为“偶数个零”

您在证明您对特定字符串0000所做的证明中犯了一个错误。您应证明所有 w≥P。 因此，您的证明仍然是不完整的

阅读我的这个答案 IN CONTEXT OF PUMPING LEMMA FOR REGULAR LANGUAGES

在该答案中，我已经解释了将 w分解为 xyz并抽取 y意味着找到循环部分并重复循环部分以生成新的语言字符串。
当我们证明某种语言是正常的时；那么实际上我们不知道循环部分在哪里，因此我们尝试满足抽引引理1,2和3的所有可能选择。

Pumping引理说，如果语言是规则且无限的，则DFA中必须存在一个循环，并且语言中每个足够大的字符串都将通过DFA的循环部分(根据 pigeonhole principle)(因此 y不能为空)。上述正式定义中的-1)。

认为，循环可以在初始位置或结束位置，因此 x和 z可以为空字符串。

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

要证明一种语言是常规的:您要证明对于 来说，所有足够长的字符串( w )在语言中至少存在一种 一种方式( y )来生成新字符串重复循环 任何次数( i )次。

要证明语言不是常规的:您将找到 至少一个足够长的字符串( w )，该字符串的语言使得没有选择 的任何方式“y” 以便可以生成新的字符串与 一起进行所有可能的重复( i )。

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)        |              |
+-------------------------+--------------------------+----------------+--------------+

警告::该规则始终无法证明“天气是否正常？”

Pumping Lemma necessary but not sufficient condition for a language to be regular. A language possible that satisfies these conditions may still be non-regular.
Reference

要证明一种语言是正常的，您可以添加一些 necessary and sufficient conditions for a language to be regular.