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

Problem Detail: 

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

Asked By : Iancovici

Answered By : Luke Mathieson

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10019