4
$\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
0
$\begingroup$

There is a straightforward proof using the more common version of the pumping lemma:

$\sphericalangle$ CFL $L, n\in\mathbb N, w\in L : |w|\ge n$

$\tilde n := \lfloor\frac{n}{2}\rfloor$

The usual pumping lemma states that:

$$\exists u,v,x,y,z : \begin{cases} w=uvxyz \\ |vxy|\le \tilde n \\ |vx|\not=0 \end{cases} \quad \forall i\in\mathbb N\ \ uv^ixy^iz\in L$$

There are three cases for emptiness of $v$ and $y$:

  • $|v|\not=0$ and $|y|\not=0$, then $(u,v,x,y,z)$ satisfies the lemma that is being proven.
  • $|y|=0$, then $(u, v, \overline x, \overline y, \overline z)$ satisfies the lemma that is being proven: $$\overline x := \varepsilon, \overline y=v, \overline z=xz$$ $$uv^i\overline x\overline y^i\overline z=uv^iv^ixz=uv^{2i}x\varepsilon^{2i}z=uv^{2i}x\varepsilon^{2i}z\in L$$ $$|v\overline x\overline y|=2|v|\le 2\frac{n}{2}\le n$$
  • $|v|=0$: same as the previous case.
$\endgroup$
  • $\begingroup$ This proof is wrong, since the usual pumping lemma states that $|vxy| \leq n$, not $|vxy| \leq \tilde n$. Hence we cannot assume that $|v| \leq n/2$ as this proof does toward the end. $\endgroup$ – xdavidliu Jul 25 '20 at 0:58

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.