0
$\begingroup$

I am having a hard time to prove it, what i know is we cannot prove that a language is regular by using pumping lemma cause even if the "pumped string" is in the language the language could still be regular.

But since we already know that ww^r is a context free language cause we can design a pda for it, we should be able to divide a string from ww^r into 5 parts and pump it and the result should still be in the language. But i fail to do so, i have done the following:

assume w = 010 then ww^r = 010010

Then, u = 0, v = 10, x = 0, y = 1, z = 0

And then i pumped it once and i got: 010100110, which obviously isn't in the language produced by ww^r which again is contradicting because we can design a pda for it

Where am i going wrong? How do i exactly use pumping lemma for CFL?

Improve this question
$\endgroup$
2
  • $\begingroup$ Please note that the pumping lemma for CFL is not meant to prove that a language is context-free. $\endgroup$
    – Russel
    May 8, 2022 at 6:56
  • $\begingroup$ You cannot prove that a language is context-free using the pumping lemma, since some languages which are not context-free also satisfy the conditions of the pumping lemma. $\endgroup$
    – Yuval Filmus
    May 8, 2022 at 8:23

1 Answer 1

Reset to default
1
$\begingroup$

The pumping lemma for context-free languages is used to prove that a given language is not a context-free language. There exists a PDA accepting the language $L = \{w w^r: w \in \{0,1\}\}$, and so $L$ is a context-free language.

The pumping lemma states that all regular languages and all CFL's satisfy a certain property: there exists a pumping length $p$ such that for every string of length at least $p$ in the language, there exists a partition of the string (into 3 parts or 5 parts) such that the pumped string belongs to the language. This property claims only that there exists a $p$ and (for every string of length at least $p$) a partition satisfying some conditions - if you choose an arbitrary value of $p$ and an arbitrary partition, the pumped strings might not be in the language.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thank you for the reply, i have one more stupid question. A language will be context free if there exist a context free grammer or / and push down automata, and we can use pumping lemma to prove "a language is not context free". So, that only leaves us with constructing a pda or cfg for the language mentioned, assume it's the language "wwr" over (0+1)* . But what if i am not creative enough to construct a pda or cfg and think that no pda or cfg exists for it ( but in reality it does ). So, is there a hard and fast algorithm or theorem that will help to check this? $\endgroup$
    – Pratik Hadawale
    May 8, 2022 at 11:04
  • $\begingroup$ Because in my original post, i tried pumping lemma for the language wwr over (0+1)* and by first assuming that the language is context free and it has "p" and can be divided into five parts and then i pumped those parts. Now, if a language is not context free then i would get a string that does not exist in the language. And i got such a string. But we do know that the language is context free since we can make a pda for it. Sorry if i sound a mess $\endgroup$
    – Pratik Hadawale
    May 8, 2022 at 11:08
  • $\begingroup$ @PratikHadawale When you say "And i got such a string" that does not belong to the language, you are supposed to get such a string for any arbitrary p and any arbitrary partition, if you want to prove a language is not context-free. Whereas, you choose a particular p and the partition yourself. $\endgroup$
    – Ashwin Ganesan
    May 8, 2022 at 11:10
  • $\begingroup$ Oh i think i got it, so you are saying even if a language is context free and we try using Pumping lemma for proving if it's "not context free" we are bound to get a such a string. So the only way to prove a language is context free is by constructing a pda or cfg. Correct? or if i am wrong can you point me to some good resources for understanding pumping lemma better? Please and Thank You! $\endgroup$
    – Pratik Hadawale
    May 8, 2022 at 11:17
  • $\begingroup$ For ways to prove a language is context-free, see cs.stackexchange.com/questions/18524/… $\endgroup$
    – Ashwin Ganesan
    May 8, 2022 at 11:40

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.