This means that proving the pumping lemma holds for a language is easy (must find an instance in whitch it holds) but proving it doesn’t hold is harder (must prove that it doesn’t hold for all instances of the language).
Asked By : Crysis85
Answered By : Yuval Filmus
- The adversary gives you an integer $p$.
- You come up with a word $w in L$ of length at least $p$.
- The adversary partitions the word into $w = xyz$, where $|xy| leq p$ and $|y| geq 1$.
- You come up with an integer $i$ such that $xy^iz notin L$.
If you win this game then you have shown that $L$ is not regular. In order to show that the pumping lemma cannot be used to prove that $L$ is regular, you have to show that the adversary wins the game. A winning strategy for you is, for each $p$, a word $w in L$ of length at least $p$, and for each legal partition $w = xyz$, an integer $i$ such that $xy^i z notin L$. This is how you apply the pumping lemma. A winning strategy for the adversary is an integer $p$ such that each word $w in L$ of length at least $p$ can be legally partitioned as $w = xyz$ in such a way that $xy^i z in L$ for all $i geq 0$. This is your goal in this exercise. If the pumping lemma doesn’t work, what does work? There is a generalization of the pumping lemma in which you mark $p$ locations of the word $w$, and then the adversarial partition $w = xyz$ must satisfy (i) $xy$ contains at most $p$ marked locations, (ii) $y$ must contain at least one marked location. Sometimes this generalized version works when the usual one fails, but not always. One method which is guaranteed to always work is the Myhill–Nerode criterion. If a language is not regular, you can always prove it (in principle) using the Myhill–Nerode theorem. In many cases it is also easier to apply than the pumping lemma, even when the latter does work. What pity that it is beyond the curricula of many courses!
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/44459
