I have a little confusion in checking whether the given language is regular or not using pumping lemma.

Suppose we have to check whether:

L.The language accepting even number of`0`

's in regular or not?

We know that it is regular because we can construct a DFA for L. But I want to prove this with pumping lemma.

Now suppose, I take a String `w= "0000"`

:

Now will divide the string as `x = 0`

, `y = 0`

, and `z = 00`

. Now on applying pumping lemma for `i = 2`

, I will get the string `"00000"`

, which is *not* present in my language so by pumping lemma its prove that the language is not regular. But it is accepted by DFA ?

Any help will be greatly appreciated

Thank you

## Best Solution

You are not completely clear about pumping lemma.

What pumping lemma say:

Formal definition:

Pumping lemma for regular languagesBut what this statement says is that:

If a language is really a regular language then there must be

some wayto generate(pump) new strings fromallsufficiently large strings.means, a string in language that is of the length ≥Sufficiently large stringP._{So it may not be possible to generate new string from small strings even if language is Regular Language}means, if language is really a regular and our choice ofSome way`w`

is correct. Then there should beat lest one wayto 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: in second point, there may be a chance that even if you breaks`w`

correctly into`xyz`

according to formal definition still some new generated strings are not in language.As you did.And in this situation you are to retry with some other possible choice of

`y`

.In you chosen string

`w`

= "0000" you can break`w`

such that`y = 00`

. And with this choice of`y`

you would always find a new generated string in in Language that is"even number of zeros"_{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}Read my this answer

IN CONTEXT OF PUMPING LEMMA FOR REGULAR LANGUAGESIn that answer, I have explained that

breakingmeans`w`

into`xyz`

and pumping`y`

finding looping part and repeating looping part to generate new stringsin language.When we proof that some language is regular; then actually we don't know where is the looping part so we try with all possible choices that satisfies pumping lemma's rule 1,2 & 3.

And Pumping lemma says that if language is regular and infinite them there must be a loop in the DFA and every sufficiently large string in language passes through looping part (according to pigeonhole principle) of DFA (and hence

`y`

can't be null. That's rule-1 in above formal definition).Think, loop can be at initial position or at end and so

`x`

and`z`

can be null strings.But actually we don't know where loop falls in DFA so we try with all possible ways.

To proof a language is regular: You are to proof that forallsufficiently long strings() in language there iswat-least(oneway) to generate new strings in the language byyrepeating looping part(any number) of times.iTo proof a language is:You are to findnotregularat least onesufficientlylong strings () in language such that therewno choice forso that its possible to generate new stringsany way 'y'with(all possiblerepetition).iCAUTION:: The Rule always not works to proof 'Weather a Language is Regular?'To proof a language is regular you have some necessary and sufficient conditions for a language to be regular.