Is this language $\{0^n1^m | (n+m) \text{is even}\}$ regular or not?

Question

$$L=\{0^n1^m | (n+m) \text{is even}\}$$

1. Using the pumping lemma , let me choose a valid string $W=0011$ $(n=2,m=2$ and $4$ is even$)$.
2. Let the number of states in the DFA ($C$) be $3$ (I find this step to be fishy)
3. $|W|\ge C$
4. Let $W=XYZ$
5. I choose $X=00,Y=1,Z=1$ such that $|xy| \le C ,|Y| \ge1$
6. So, for all $i$, $00(1)^{i}1$ should be in $L$
7. But when $i=2$,String $00111$ is not in $L$, hence this language is not regular.

But I came across a regular expression for the same language:

$$0(00)^*1(11)^*+(00)^*(11)^*$$ Is there a flaw in my pumping lemma or the regular expression? Someone please help me out.

Answer 1

You seem to have misunderstood the pumping lemma.

Taking the definition from Introduction to the Theory of Computation by Michael Sipser

If $A$ is a regular language, then there is a number $p$ (the pumping length) where if $s$ is any string in $A$ of length at least $p$, then $s$ may be divided into three pieces, $s = xyz$, satisfying the following conditions:

1. for each $i ≥ 0, xy^i z \in A$,

2. $|y| > 0$, and

3. $|xy| \le p$.

A few points:

• The lemma only says that a pumping length $p$ exists. You do not get to choose the value of $p$. So, you cannot say that let $p=3$.
• For every string $s$ in the language with length at least $p$, it may be divided into three pieces, $s=xyz$. Notice that this again talks only of the existence of a way to split $s$ into $xyz$ given that $A$ is regular. So, you do not get to choose how the string splits into $x$, $y$, and $z$ in the general case. Finding a split that does not satisfy the conditions does not show that the language is not regular. You need to find such a string that cannot be split as stipulated by the definition to show that a language is not regular.
• Finally, the pumping lemma does not say what happens if $A$ is not regular. So, even a non-regular language may satisfy it, and the pumping lemma cannot be used to show that a language is regular.

Answer 2

You pumping lemma is wrong. The pumping lemma only works on strings that are sufficiently long, yours is not. If we have a string that is sufficiently long(longer then the number of states in the corresponding dfa or nfa) we must have repeated some states, which means that there is a loop somewhere in the path through the dfa to generate this string. We can then infinity repeat this loop and the string is still valid. Your string of length 4 is not sufficiently long to use the pumping lemma on. The language is regular. There are only 2 situations regarding valid strings in this language. If the number of 0's is even, the numbers of 1's is even. And if the number of 0's is odd the number of 1's is odd. Your regular expression covers both of these.