# Robustness of non-context-free proof against trivial manipulation

First, we state here a theorem that is well-known in computability theory:

$$L=\{xx\mid x\in\Sigma^*\}\notin CFL$$ for every fixed $$|\Sigma|\geq2$$

And, the standard proof is using pumping lemma. At first sight, we rarely face the language $$L$$ exactly as defined above in a broader theoretical research. Instead, what might be more frequent is $$L'=\{\text{some-simple-manipulation}(x)x\mid x\in\Sigma^*\}$$ Perhaps, those simple manipulation are necessary for unambiguous encoding. For example, symbol doubling, prefix, postfix, etc. Those are quite frequent and unavoidable.

Now, the question is: Can the above theorem still hold under these simple manipulations?

Symbol doubling (as commented below) is a good starter, if one feels the question too broad.

Or even worse, there may be some simple manipulation that push $$L$$ down to CFL again.

• Unless you specify the simple manipulations, the question will be hard to answer. Does reverse count, for example? For other manipulations, I would guess that standard closure properties would show that the modified languages are still not context-free. Oct 18, 2018 at 7:19
• Take symbol doubling as a starter, $001011$ indicates $011$ (the second in each pair terminates the current string) Oct 18, 2018 at 7:21
• Note that PDA is only one-direction less from being Turing-complete. Oct 18, 2018 at 7:22
• I don't understand what symbol doubling is. Could you please explain more? Oct 18, 2018 at 9:31
• @xskxzr I guess it means duplicating each symbol of the alphabet, e.g. $x=abcde$ to $x'=aabbccddee$.
– chi
Oct 18, 2018 at 12:51

## 1 Answer

Note $$\left\{x^{\mathrm{R}}x\mid x\in\Sigma^*\right\}$$ is context free, where $$x^{\mathrm{R}}$$ means the reverse of $$x$$.

Or even worse, there may be some simple manipulation that push $$L$$ down to CFL again.

So if you consider reversing as a simple manipulation, the answer is indeed yes.

• I just realize that symbol doubling like in my question can still be pumped to contradiction. Oct 18, 2018 at 14:31