Let L be a language that fulfills the properties implies by the Pumping lemma for regular languages. Does L necessarily fulfill the corresponding properties of the Pumping lemma for context-free languages as well?

  • $\begingroup$ Ok, if you didn't manage to contradict it, how about a proof that it is correct? $\endgroup$ – Shaull Jun 30 '15 at 16:21
  • 1
    $\begingroup$ Yes, it is true. Try to provide some details in your question about how you approach the problem, and where you got stuck. This will make an answer much more productive. $\endgroup$ – Shaull Jun 30 '15 at 16:40
  • 1
    $\begingroup$ What do you mean by "a language that fulfils the pumping lemma"? The pumping lemma is a fact about regular languages. It's not something that is fulfilled or not fulfilled by any particular language, just as, for example, Fermat's last theorem is neither fulfilled nor not fulfilled by any particular natural number. $\endgroup$ – David Richerby Jun 30 '15 at 17:01
  • 2
    $\begingroup$ @RickDecker "If $L$ is regular, then the PL applied to $L$ is true." No, the pumping lemma isn't "true for a language $L$": it's just true. It's a universal statement about languages, with no free variables: for all $L$, if $L$ is regular then $L$ has property $X$. For any specific language, one can look at the hypothesis and conclusion of that implication but is that "applying the pumping lemma to $L$"? When we use the pumping lemma to prove non-regularity, we use the contrapositive: for all languages $L$, if not $X$ then $L$ is not regular. What is "applying the PL to a language"? $\endgroup$ – David Richerby Jun 30 '15 at 20:36
  • $\begingroup$ Hint: look at the respective proofs. $\endgroup$ – Raphael Jun 30 '15 at 20:56

Before giving the answers, some discussion on your direction for the proof:

It is highly unlikely that a proof of this claim would use the containment $REG\subseteq CFL$, since the pumping lemma is not an exact characterization, and if a language satisfies the regular pumping lemma, it doesn't proof that the language is regular.

Thus, the proof will have to go into the "guts" of the lemmas. Now for the proof:

Consider a language $L$ that satisfies the regular pumping lemma. Thus, there exists some $p>0$ such that for every word $w\in L$, if $|w|>p$, then there exists a partition $w=xyz$ such that $|xy|\le p$, $|y|>0$ and for every $i$ it holds that $xy^iz\in L$.

We want to prove that there exists some $q>0$ such that for every word $w\in L$, if $|w|>q$, then there exists a partition $w=uvstr$ such that $|vst|\le q$, $|vt|>0$ and for every $i$ it holds that $uv^ist^ir\in L$.

Seeing things stated as above, the rest is just "pattern matching": Let $q=p$, and consider a word $w\in L$ such that $|w|>q$, then there exists a partition $w=xyz$ as above. Let $u=x,v=y,s=\epsilon,t=\epsilon$, and $r=z$. Clearly $uvstr=xyz=w$. Also, $|xy|\le p$, so $|vst|=|y|\le p$ and $|y|>0$ so $|vt|=|v|=|y|>0$. Finally, for every $i$ it holds that $$uv^ist^ir=xy^iz\in L$$ and we are done.


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.