1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 29 '18 at 15:03
  • $\begingroup$ 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$. $\endgroup$ – Yuval Filmus May 29 '18 at 15:05
  • $\begingroup$ Trial and error. $\endgroup$ – Raphael May 29 '18 at 16:48
3
$\begingroup$

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:

  • you win by successfully proving that the language isn't regular;
  • you find that the proof doesn't work, and if the reason is the one I'm expecting, it should guide you straight to a better string to try to pump.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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