Pumping lecture for regular language

Question

I have a little confusion about checking if a given language is regular or not using the pumpdown lemma.

Suppose we have to check:

L. A language taking an even number 0 in regular or not?

We know that it is regular, because we can build a DFA for L. But I want to prove it using the pumping lemma.

Now suppose I take the string w= "0000" :

Now split the line as x = 0 , y = 0 and z = 00 . Now, applying the pump lemma for i = 2 , I get the string "00000" , which is not in my language, therefore, passing the lemma, proves that the language is not regular. But is this accepted by the DFA?

Any help would be greatly appreciated.
thank you

Answer 1

You do not quite understand the pumping lemma.

What the rolling lemma says:

Formal Definition: Pumping Lecture for Common Languages

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

• | y | ≥ 1 | ≥ 1
• | xy | ≤ | ≤ p
• for all i ≥ 0 , xy i z ∈ L

But this statement says that:

If the language is really an ordinary language, then there must be some way to generate (pump) new lines from all sufficiently large lines.

• A sufficiently large string means a string in a language that has a length ≥ P.
  _{Thus, it cannot generate a new line from small strings, even if the language is an ordinary language}

• A certain way means that the language is indeed regular, and our choice of w correct. Then there must be one way to break w into three parts xyz in such a way that by repeating (pumping) y for any number of times, we can generate new lines in the language. _{the right choice of w means: w in the language and large enough ≥ P}

note: at the second point, it may be possible that even if you correctly broke w in xyz according to the formal definition, some new generated lines are still not in the language. Just like you.

And in this situation, you must repeat another possible choice of y .

In the line you choose w = " 0000 " you can break w so that y = 00 . And with this choice of y you will always find a new generated string in the language, which is an "even number of zeros"

_{One mistake you make in your proof that you make for a specific line is 0000. You must confirm all w ≥ P. So your proof is incomplete sub>}

Read my answer IN THE CONTEXT OF TENSION LEMMA FOR REGULAR LANGUAGES

In this answer, I explained that splitting w into xyz and pumping y means finding a loop and repeating a loop to generate new lines in the language.
When we prove that some language is regular; then in fact we don’t know where the cycle point is, therefore we try with all possible options that satisfy the rule of the transfer lemma 1,2 and 3.

And the pumping lemma says that if the language is regular and infinite, there should be a cycle in DFA, and each sufficiently large line in the language goes through a part of the cycle (according to the principle of pigment holes ) of DFA (and, therefore, y cannot be zero. This is rule 1 in the above formal definition).

Think about it, the loop can be in the starting position or at the end, and therefore x and z can be empty.

But we don’t really know where the loop gets into the DFA, so we try our best in every possible way.

To prove the correctness of the language : you have to prove that for all sufficiently long lines ( w ) in the language there is at- the smallest one way ( y ) to generate new lines in the language by repeating part of the loop any number ( i ) times.

To prove that the language is not regular : you must find at least one sufficiently long line ( w ) in the language, so that there is no choice for 'y' in any way , so that it can generate new lines with possible repetition ( 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) | | +-------------------------+--------------------------+----------------+--------------+ 

CAUTION:. Does the rule always fail to prove "Weather when the language is ordinary"?

Pumping Lemmas is necessary, but not a sufficient condition for the regularity of the language. A language that satisfies these conditions may be irregular.
Link

To prove that a language is regular, you have the necessary and sufficient conditions for a regular language.