You are not completely clear about pumping lemma.

What pumping lemma say:

Formal definition: **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:

`|`

`y`

`| ≥ 1`

`|`

`xy`

`| ≤`

`p`

- for all
`i`

`≥ 0`

, `xy`

^{i}`z`

`∈`

`L`

But what this statement says is that:

If a language is really a regular language then there must be *some way* to generate(*pump*) new strings from **all** *sufficiently large strings*.

*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}

*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*: 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 LANGUAGES**

In that answer, I have explained that *breaking *`w`

into `xyz`

and pumping `y`

means *finding looping part and repeating looping part to generate new strings* in 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 for *all** sufficiently long strings*(*w*) in language there is *at-least ***one** way(*y*) to generate new strings in the language by *repeating looping part ***any number** (*i*) of times.

**To proof a language is ***not* regular:You are to find *at least one** sufficiently* long strings (*w*) in language such that there *no choice for ***any way 'y'** so that its possible to generate new strings *with ***all 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:**: The Rule always not works to proof 'Weather a Language is Regular?'

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

To proof a language is regular you have some necessary and sufficient conditions for a language to be regular.

## Best Solution

If you can correctly describe your language L by an NFA or DFA, then it will be regular.

There is a well known equality of NFAs, DFAs, regular grammars and regular expressions, so a representation of L in any of these formalisms should do.