0
$\begingroup$

I have a doubt related to pumping lemma in CFL for which I dont find an answer, so I think is very easy because no one wonder about. The lemma says:

For every context-free language L, there exists a number m such that for every long string s in L (|s| > m

My doubt is: Is there any restriction related to strings u (the most left) and y (the most right), I mean can they be empty?.

In case they can, I cannot proof that a^nb^n is context-free because, for p=3, I could make vwx only a's or only b's and when pumping there will be different quantity of a's and b's.

Thanks

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

They can be empty, but the pumping lemma is used to prove that a language is not context free.

It says that if a language is context free, such a configuration always exists, and it's the case for $a^nb^n$ as one can take $u=a^{n-1}, v=a, w=\varepsilon, x=b, y=b^{n-1}$. The lemma says that one such configuration exists, not that all configurations work.

To prove that $L$ is context free you would have for example to provide a context free grammar generating it.

Improve this answer
$\endgroup$

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.