How can I prove the next claim:

If a language $L$ meets the pumping lemma for regular languages then $L$ meets the pumping lemma for context-free languages?

(Without any pre-condition about the regularity of $L$)


1 Answer 1


The pumping lemma of context-free languages means finding $x,y,z,v,u$ such $w=xvyuz, |vu|>0,|vxu|\le p$, and for all $n\in\mathbb N$, $xv^nyu^nz$

The regular pumping lemma means finding only $v,y,u$ where $w=abc,|b|>0,|ab|\le p$ and $ab^nc\in L$. ("a","b","c" here are representing sub-words of w)

So, simply take $x=a,v=b,y=c,u=\epsilon,z=\epsilon$


Your Answer

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

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