# How to apply the pumping lemma to $\{0^m 1^n \mid 2n \leq m \leq 3n, m,n \geq 0 \}$?

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$?

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

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.

-