0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – J.-E. Pin Nov 11 '18 at 18:49
  • $\begingroup$ 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. $\endgroup$ – Peter Leupold Nov 11 '18 at 19:20
  • $\begingroup$ I'm so sorry Peter! I meant not contextfree. And thank you so much for your answer. I'll study it. :) $\endgroup$ – Mugumble Nov 11 '18 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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