1
$\begingroup$

This question already has an answer here:

I am new to automata theory.

Could you give me a little hand with the correct use of the pumping lemma? I understand now how to proof a language is not context-free, but how do I use the pumping lemma to proof it is?

Do I find one way to break the word into: uvwxy so that v and x can be pumped? Is that enough and can I pick it in such a way that u or w or y are empty. I understand from the lemma that as long as v or x are not empty it is good. But can only w be empty and the rest be at least one character?

I did read on this topic, but I am just trying to make sure that what I understood is correct and there aren't other not so obvious things I should consider. Please help.

$\endgroup$

marked as duplicate by D.W., Luke Mathieson, David Richerby, André Souza Lemos, Ran G. Jun 15 '15 at 23:17

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Thank you, but the other question only gives me half the answer. I edited the question to only ask about the other half: proof that the language is context-free. $\endgroup$ – Justina Jun 15 '15 at 6:07
  • 1
    $\begingroup$ Read about the "game" in the first answer to cs.stackexchange.com/q/265/755. That will answer your question You don't get to pick $u$ or $w$ or $y$. $\endgroup$ – D.W. Jun 15 '15 at 6:10
  • $\begingroup$ Sorry, but I really don't get it :(. It means it cannot be |w| = 0 for example? $\endgroup$ – Justina Jun 15 '15 at 6:14
3
$\begingroup$

I read How to prove that a language is not context-free? and it has a very detailed example of a demonstration using the pumping lemma. But you are looking for some general understanding of the method so I will tell you the steps I follow when I use pumping lemma to prove that $L$ is not CFL:

1) You suppose that $L$ is CFL. The idea is find a contradiction using the pumping lemma.

2) By pumping lemma exists a constant $N>0$ associated to $L$. Use a generic constant because if you use a fixed one like $N=1$ for example, and don't find a contradiction you have to try with $N=2,3,4,...$.

3) You have to choose a word $\sigma \in L$ such that $|\sigma|\geq N$. You have to use your creativity to choose a word that allows you to easily reach a contradiction in the next steps.

4) By the pumping lemma exists a factorization of your word $\sigma=uvwxy$ and the following always complies: $$|vwx|\leq N$$ $$|vx|\geq 1$$ $$\sigma_i=uv^iwx^iy \in L \forall i\in\mathbb{N}_0$$

5) So the next step is to prove that the factorization does not exists. Your job if to check that all possible factorizations in the form $uvwxy$ don't complies with the 3 points of the pumping lemma. This generate a contradiction in your initial assumption then $L$ can't be CFL.

6) If you find a factorization of your particular word this mean nothing! Remember that the pumping lemma says:

If $L$ is CFL $\Rightarrow$ exist a factorization$\dots$

So you have two options at this point. The first is suspect that maybe your language is CFL and try to write a context-free grammar or draw a push-down automaton that denotes $L$. In second option you can assume that the word $\sigma$ was bad pick and try with another word to find a contradiction.

This is the general mechanics of the pumping lemma. I recommend you to try to understand the theory behind it or you will probably make mistakes in your test.

You can't use the pumping lemma to show that a language $L$ is context-free.. If you want to prove that $L$ is CFL the standard way is to write a CFG or draw a PDA like I said before.

$\endgroup$
  • $\begingroup$ Thank you very much, your answer helped me understand the steps. (6) worries me a little, but I hope to chose a good word. $\endgroup$ – Justina Jun 15 '15 at 7:03
  • 1
    $\begingroup$ If you do some exercises you will polish your ability to choose good words. $\endgroup$ – Renato Sanhueza Jun 15 '15 at 7:11

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