Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
To prettify, use \$latex\$. But before, what is (00) ? –  user1938185 Mar 17 '13 at 0:49
    
You can use $\LaTeX$ to prettify your answer. This meta post describes how to get started. I've also put through an edit to clean up your post for you. –  George V. Williams Mar 17 '13 at 0:58
    
Thanks for the clean up. @user1938185 (00) is just part of the language L. –  n00b1990 Mar 17 '13 at 12:16

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
Thank you for your answer. I also edited the post to improve readability, it should be better to read now. I guess to prove the non-regularity I have to show that there are more 0's then 1's. I understand now, thank you –  n00b1990 Mar 17 '13 at 12:40
1  
@n00b1990: It’ll be a little more complicated than that. If $n$ is odd, then $xy^2z$ will have an odd number of $0$’s and therefore won’t be in $L$. If $n$ is even, see what happens when $i=0$. (And you’re welcome.) –  Brian M. Scott Mar 17 '13 at 17:22

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.