# Language of lists of words, not all of which are different, is not context-free

How do I prove that the following language isn't context-free using the pumping lemma? $$L=\{w_1\#w_2\#\dots\#w_k \colon k ≥ 2, w_i \in \{0,1\}^*, w_i = w_j \text{ for some } i \ne j\}$$

I am having trouble choosing the string to use for the proof. I know that I have to choose a string such that at least two substrings separated by the # are equal to each other but am unsure of how to approach this. If someone could please help me with this, I would appreciate it.

## 1 Answer

If $$L$$ were context-free then so would $$L' = d(L \cap (0+1)^*\#(0+1)^*)$$ be, where $$d$$ is the homomorphism that deletes $$\#$$. However, $$L'$$ is the language of squares (words of the form $$w^2$$), which is well-known not to be context-free.

If for some reason you have to prove that $$L$$ is not context-free directly using the pumping lemma, this suggests looking at the proof that $$L'$$ is not context-free and trying to adapt it.

• I am required to use the pumping lemma here. My issue with it is choosing the string, and after looking at it again, I am not too sure what the contradiction I am trying to make should be. – binarycoffee356 Jun 19 '20 at 21:48