# Pumping Lemma for CFL

So I solved some exercises where I have to use the pumping lemma for contextfree languages but this one is a problem for me:

Consider:

$$L =$$ { $$w_1£w_2£w_3 \in$$ { $$0,1,£$$}$$^*$$ | $$w_1, w_2, w_3 \in$$ {0,1}$$^*$$ and $$\exists i \neq j \in$${$$1,2,3$$} : $$w_i = w_j$$ }.

Show that: L is not contextfree.

So L contains words, which are separated with £ and atleast two subwords are the same. My idea is that we create a word ( with the help of the pumping lemma ) that has three different subwords $$w_1, w_2, w_3$$. But I don't find a "start-word". My first idea was to consider z:= 0.....0£0.....0£1.....1. But the problem is this part $$uvwxy = 0.....0£0.....0£1.....1$$ . If I pumped only the 1....1 part,then I wouldnt have a counterexample. So can you please tell me which word is a possible start-word?

## 1 Answer

The definition of $$L$$ allows $$w_1$$, $$w_2$$ and $$w_3$$ to be empty. By chosing one of them to be empty you avoid the problem you have with being able to pump in the "$$1\dots 1$$ part".

But this is not enough. You cold pump zeroes in both $$w_1$$ and $$w_2$$ and thus stay within the language.

For $$n$$ the constant from the pumping lemma, take for example $$0^n1^n£0^n1^n£.$$

If you want to pump in both $$w_1$$ and $$w_2$$, it can only add $$1$$s to the former $$0$$s to the latter destroying the equality.

• Pumping lemmas can be used to prove that a language is not context-free and are useless to prove that a language is context-free. – J.-E. Pin Nov 11 '18 at 18:49
• Right, @J.-E.Pin. And the cited problem statement indeed asks for a proof of context-freeness. But the OP asks for a start word to use the pumping lemma (and have a counterexample). So it seems to me that he really wants to show that the language is not context-free although admittedly he does not state that explicitely. – Peter Leupold Nov 11 '18 at 19:20
• I'm so sorry Peter! I meant not contextfree. And thank you so much for your answer. I'll study it. :) – Mugumble Nov 11 '18 at 20:15