# Which word to pump in pumping lemma?

Let say we have a Language $L = \{0^m1^n \mid m,n \geq 0 \land m \neq n \}$. If I want to use the pumping lemma to disprove that the language is regular or context-free, how do I choose the word in dependence of the number $n$? The problem is that I got an $m$ and an $n$ in the exponent and they cannot be equal. Can I choose $0^{n+1}1^n$ for the word?

• Which word you choose is up to you. To check whether a given word works, you need to check whether you can complete the proof using this word. There isn't really any way to tell in advance. – Yuval Filmus May 29 '18 at 15:03
• In your case, the word $0^{n+1} 1^n$ won't work, since I can choose the decomposition $x=\epsilon$, $y=0^2$, $z=0^{n-1}1^n$ (assuming the pumping constant is at least 2), and then $xy^iz \in L$ for all $i$. – Yuval Filmus May 29 '18 at 15:05
• Trial and error. – Raphael May 29 '18 at 16:48

You can use any word in the language that lets you complete a proof. The pumping lemma says that, if a language $L$ is regular/context-free, then every long-enough string in the language can be partitioned in a way that generates an infinite set of strings that are also in $L$. So, if you can find any string in $L$ where the partition generates strings outside $L$, you're done.
Finding the right string to start with requires some thought and creativity; I'm not aware of any general method for doing it. I've not written anything out but I think that, if you start with $0^{n+1}1^n$, the proof won't work. However, you should try doing the proof with that string. Assuming that you don't make any mistakes, there are two possible outcomes: