Is this proof using the pumping lemma correct?

Question

I have this proof and it goes like this:

---

We have a language $L = \{\text{w element of } \{0,1\}^* \mid w = (00)^n1^m \text{ for } n > m \}$.

Then, the following proof is given:

There is a $p$ (pumping length) for $L$. Then we have a word $w = (00)^{p+1}1^p$ and $w$ element of $L$ and $|w| \le p$. $w$ can be written as $xyz$ with $y$ not empty and $|xy| \le p$.
This implies that $y=(00)^n$ for $0 < n \le p$.

Now for all $i \ge 1$ it means $xy^iz = (00)^{p+n(i-1)+1}1^p$ is an element of $L$.
Hence $L$ is regular.

---

I can clearly see that this proof is wrong (at least that's what I think). I can see that three things are wrong:

1. The pumping lemma cannot be used to proof the regularity of a language!
2. One thing bothers me: $y=(00)^n$ could never hold for $0 < n \le p$ because $n$ can be $p$ and therefore $y=(00)^p$ which means that the length of $y$ is $2p$! Condition no. 2 of the pumping lemma won't hold because $|y| = 2p$ and the 2nd condition of the pumping lemma is $|xy| \le p$.
3. Another thing is that you should also consider $i = 0$. Oh, and if $i = 0$ and $n \ge 1$ we would get that $n \le m$ and not $n > m$!

My question is actually if my assumptions are correct because it didn't take me much time to figure this out. There is a chance that I missed something. Can someone clarify?

I'm not asking for a proof, so please don't give one. I just want to know if my assumptions are correct and if not what you would think is wrong?

Answer 1

A comment before I get to your (1)-(3): $p$ and $P$ are not the same symbol, so either the pumping length is $p$, or it’s $P$, but you shouldn’t keep jumping back and forth between the two. I’ll use $p$.

1. This is correct: the pumping lemma is strictly a tool for showing that a language is not regular.

2. This objection is not really well-taken. It’s true that $n$ cannot be $p$, for the reason that you give, but that does not invalidate the statement that $y=(00)^n$ for some $n$ satisfying $0<n\le p$, which is what is actually intended there; after all, the fact that $2\ne 3$ does not invalidate the statement that $2=n$ for some $n$ satisfying $0<n\le 3$. However, we cannot actually conclude that $y=(00)^n$ for some $n$, because there’s no reason to think that the length of $y$ has to be even. What we can legitimately conclude is that $y=0^n$ for some $n$ such that $0<n\le p$.

3. Yes, one should always remember that $xy^iz$ is supposed to belong to $L$ for all non-negative integers $i$, including $i=0$; sometimes this is crucial to using the pumping lemma to prove that a language is not regular.

In fact if you correct the errors in this argument, you’ll have a proof that this $L$ is not regular.

Answer 2

Yes, the proof is bogus, as Brian M. Scott's answer expertly explains.

It is easier to prove that the reverse of your language isn't regular, or (by minor adjusting the proof of the lemma to place the pumped string near the end, not the start) that it isn't regular.