0
$\begingroup$

1 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?

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

Some strings in your language are pumpable, others aren't. You have to look for one that isn't pumpable. Use the fact that the relevant piece is of limited length.

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.

$\endgroup$

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.