1
$\begingroup$

Let $G$ be any CFG Grammar. There exists number $K$ dependent to $G$ so that for each $w\in L(G)$ with length bigger or equal than $K$, we can be write $w=uvxyz$ such that $uv^nxy^nz \in L(G)\; \forall\,n\geq 0$ and $|vy|\geq 1$.

My question is that this statement does not include the case of $|vxy|\leq K$. Should it be included for the theorem completeness, or is it redundant and it is indeed a special case (my professor did not include it e.g. but on Wikipedia and other books I always see that they include it)?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

It is odd that your professor taught you a weaker version of pumping lemma for context-free languages. I would believe it was unintentional.

As noted in the question, the condition $|vxy|\le K$ where $v\ y$ is the pumpable part and $K$ is the pumping length is included in the standard pumping lemma for context-free languages on this Wikpedia page or in common relevant introductory textbooks.

While the weaker version is correct, it is less useful and less powerful for proving a language is not context-free.

  • That condition makes it easier to prove many a language is not context-free.
  • There are languages that satisfy the weaker version but not the standard version. For example, the non-context-free language $$\{w\#t\mid w\text{ is a substring of }t,\text{ where }w, t\in\{a, b\}^*\}.$$

It takes little extra work to prove the standard version than the weaker version. It does not make much sense to deviate from the common practice that includes that condition in the pumping lemma.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Yes, my wrong of course I meant either one of v, y not empty (I edited it in main post). Also bigger or equal than K. The only missing was the original case I wrote. $\endgroup$
    – dvox
    Jun 8 at 5:06
  • $\begingroup$ So are both versions equivalent? I mean can I prove everything I could with $|vxy|\leq K$ and without that condition? $\endgroup$
    – dvox
    Jun 8 at 5:17
  • $\begingroup$ @dvox Please see my update. $\endgroup$
    – John L.
    Jun 8 at 19:03
  • $\begingroup$ Ok, great thanks! $\endgroup$
    – dvox
    Jun 8 at 21:35
  • $\begingroup$ The language of words over alphabet $\{a,b,c,d\}$ having the same number of $a$s and $b$s as well as the same number of $c$s and $d$s is another non-context-free language that satisfies the weaker version but not the standard version. $\endgroup$
    – John L.
    Jun 21 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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