1
$\begingroup$

I am studying CFL at the moment and I found this confusing. What I've just read is that, $L=\{ww\}$ is not a CFL. The proof showed it by using pumping lemma for CFL. ($w=0^n1^n0^n1^n$) and I fully understood the proof.

Here comes the question. I understand that $L1=\{ww^R\}$ can be constructed by NPDA, and thus a CFL. However, if I use pumping lemma for this, i.e., $w=0^n1^n1^n0^n$, I can show that this specific sentence does not satisfy pumping lemma as well.

Pumping lemma

Let $L1$ be a CFL. Then, there exists n such that for any $w ∈ L$ and $|w|\geq n$, $w$ can be decomposed as $w=uvxyz$ such that

1) $|vxy|\leq n$

2) $|vy| \geq 1$

3) $w_i=uv^ixy^iz$ ∈ $L1$, for all $i \geq 0$

By setting $w=0^n1^n1^n0^n$ and if $v,y$ ∈ $0^+$ in the first half, regardless of how many times I pump, $ww^R$ does not belong to $L1$ anymore. Thus, since the pumping lemma should be satisfied for every possible case, I can conclude that it is not CFL.

Note again that I know $L1$ can be designed with NPDA. What is my mistake while proving using pumping lemma?

I am really confused about this. Can anyone answer my question?

My first guess is...

In order to show a language is CFL, I should first try to construct a PDA accepting the language, and if it is not possible, I should show that it is not a CFL by using pumping lemma. However, what if I could not find a PDA although there exists one?

P.S. I actually posted this question yesterday with not much detailed explanation, therefore I posted again.

Thanks in advance

Improve this question
$\endgroup$
2
  • $\begingroup$ You previously got one comment that answered the second part of your question: cs.stackexchange.com/questions/51567/… $\endgroup$
    – D.W. ♦
    Jan 8, 2016 at 4:22
  • 1
    $\begingroup$ Why have you not edited the older question? $\endgroup$
    – Raphael ♦
    Jan 8, 2016 at 11:48

1 Answer 1

Reset to default
3
$\begingroup$

You are right in one thing. You can't pump the first half. But you clearly are confusing the pumping lemma for CFL with the version for regular languages. As you wrote the decomposition of $w$ is $uvxyz$. You can use a large substring $u$ to pump in the second half of $w$ but that generate the same conclusion as pumping the first half. What to do then? You can pump in the half of the word. Each time you add a 1 in the first half you can add a 1 in the second half so the decomposition exist and you can´t say that $L1$ is not CFL.

Summarizing the decomposition exists. For example:

$u=0^n1^{n-1}$

$v=1$

$x=\epsilon$

$y=1$

$z=1^{n-1}0^n$

So we can't conclude anything from the pumping lemma. It is time to choose another word to try it again or generate a PDA to prove that $L1$ is CFL.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for the answer. So what you are saying is that since there is the case where $w$ belongs to $L1$ even after pumping as you showed above, I cannot conclude that it is not CFL. Am I right? $\endgroup$
    – Mansumen
    Jan 8, 2016 at 2:51
  • 1
    $\begingroup$ That is the crux of the answer. When the PL says that $w$ "can be decomposed such that...", it means that there is at least one decomposition with the required property. $\endgroup$
    – Klaus Draeger
    Jan 8, 2016 at 12:36
  • $\begingroup$ And as the answer says, there are languages which do satisfy the pumping lemma, but aren't context free (or regular, whichever pumping lemma you use). $\endgroup$
    – vonbrand
    Jan 8, 2016 at 13:49

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.