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 1


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.

  • $\begingroup$ 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. $\endgroup$ Jun 19, 2020 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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