3
$\begingroup$

So I'm trying to understand the pumping lemma for CFL ( context free languages ).I've already used it to show that a language is not contextfree and I have considered the proof of this lemma (see the PDF below ) Now I've read that there is a variant of the pumping lemma for context free languages. You replace the condition " $ vy \neq \varepsilon $ " with " $v$ and $y$ are not $\varepsilon$". Like I've said. Here is the proof of the"normal" pumping lemma for CFL.

https://www.google.de/url?sa=t&source=web&rct=j&url=https://cs.uwaterloo.ca/~watrous/CS360.Spring2017/Lectures/10.pdf&ved=2ahUKEwjs_PfAluHeAhWCzKQKHR6BDgwQFjAKegQICRAB&usg=AOvVaw14bQTaIb205pRrv2NpsGGX

What do I have to change for the variant of the pumping lemma?

$\endgroup$
  • $\begingroup$ There are some stronger variants of the pumping lemma like the Ogden Lemma or the Bader-Moura Lemma. Concerning the variant you mention, it can certainly not be proved for the same constant. I even doubt that it is possible at all, already for the simple fact that people would probably use this stronger variant. $\endgroup$ – Peter Leupold Nov 20 '18 at 10:55
  • $\begingroup$ However, my first idea was this one: Take a larger constant that guarantees the existence of two non-interleaving loops in the derivation. If one of them produces pump factors on either side, take it for the proof of the lemma as before. If both produce non-terminals only on one side, take these two factors for the pumping. Here not just all $uv^iwx^iy$ are in the language, but all $uv^iwx^ky$; but the latter of course implies the former. So this kind of pumping is maybe not in the original spirit, but it still works. $\endgroup$ – Peter Leupold Nov 20 '18 at 10:56
  • $\begingroup$ The constant might be significantly bigger and more complicated to calculate for a given grammar. More importantly, you loose the condition $|vwx|<c$ for the constant c, because the two loops might be far apart. Probably you can guarantee that one loop is below the other - but this makes the calculation of the constant even more complicated. $\endgroup$ – Peter Leupold Nov 20 '18 at 10:57

Your Answer

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

Browse other questions tagged or ask your own question.