# Why is this language *not* pumpable? (language = arbitrary word followed by exact same arbitrary word)(pumping lemma for context-free-languages)

language = arbitrary word followed by exact same arbitrary word = u * u (with u being out of non-empty words of alphabet {0, 1} )
(sorry for the formatting, see screenshot-link for conventional/clear expression)

The purpose is to prove that the given language is not a context-free-language (using the pumping lemma).

So i thought that this language should definitely be pumpable, since you can choose x and z as corresponding parts in one of the u/"halves". So if word to be pumped is "0101" then you choose e.g. x=1 (0101) and z=1 (0101) and the remaining parts that stay static are assigned with u=0 (0101), y=0(0101), and v=empty.
If pumped zero-times/i=0 word reads: 00
i=1: 0101
i=2: 011011
i=3: 01110111
(and so on)

(For more complicated words you would need to use all three (u, y, v), but the basic principle would still be that x and z are assigned corresponding parts of the word and u,y,v would be assigned the remainder. (This doesn't work for the extremely small words 00,01,10,11 that would become empty when zero-pumped, but as long as the exceptions are finite / of finite/fixed number this isn't a problem AFAIU.)
Clearly this is wrong, but can anybody explain how/why?

• You might have to use the fact that $|xyz|$ is bounded (assuming I got your notation right). – Yuval Filmus Aug 10 '20 at 22:24

In your case, say the pumping length is $$N$$, and take $$\sigma = 0^N 1^N 0^N 1^N$$. You'll find that however you position the part that gets pieces repeated, you won't be able to increase the first and second stretch of $$0$$ or of $$1$$, or get the correct repeat by pumping around one of the $$0/1$$ boundaries.