Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I'm not really sure the how you would go about proving this language isn't regular with the pumping lemma:

$L= \{0^m 1^n | 2n \leq m \leq 3n, m,n \geq 0 \}$

Does this indicate that $S = 2$, so we start by by using a string $\geq 2$?

share|improve this question
    
Welcome to Computer Science! Your question is a very basic one. Since you did not include much of an attempt to solve it on your own, we have litte to work with. Let me direct you towards our reference questions which cover your problem in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Your question may then be reopened. Good luck! –  Raphael Feb 22 '13 at 8:18
    
Are you sure that you have not made a mistake in writing $2n \ge m \ge 3n$? If there is no mistake, what can you say about $m$ and $n$? –  Paresh Feb 22 '13 at 12:57
    
Sorry had it backwards, but it is $2n \leq m \leq 3n$ and $m,n \geq 0$ for $0^m 1^n$ –  echad Feb 22 '13 at 13:16
2  
Take $m$ longer than the pumping length and pump it out of the bounds. –  Karolis Juodelė Feb 22 '13 at 15:31
    
So let's say we go with n=2, m=4 $000011$ $xyz$ => $ x=00, y=00, z=11$ ... now what? –  echad Feb 22 '13 at 16:32

1 Answer 1

up vote 2 down vote accepted

For pumping lemma proofs, we have to remember that only strings longer than the pumping length are guaranteed to be "pumpable" (if the language is regular). Unfortunately we don't (typically) know what the pumping length is, so we have to work a little more abstractly than picking a fixed length string.

In this case, given pumping length $p$, we can take the string $s=0^{3p}1^{p}\in L$ (i.e. we choose the string where $n=p$ and $m=3n=3p$). Now if $L$ were regular, we'd be able to divide $s$ up into three parts $s=xyz$ where:

  • $|xy|\leq p$
  • $|y| > 0$
  • $xyz \in L \Leftrightarrow xy^{i}z\in L $ for all $i\in\mathbb{N}$

So with our $s$, we know that $y$ must be a string of $0$'s, as $y$ is non-empty and is a subtring of the first $p$ characters.

Then if we pump up (never forget that pumping down is also a possibility - consider $0^{2p}1^{p}$) we get the string $s'=0^{3p+|y|}1^{p}$. As $|y|>0$, clearly $s' \notin L$, which contradicts the pumping lemma, therefore $L$ cannot be 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.