0
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Oct 18 '18 at 7:19
  • $\begingroup$ Take symbol doubling as a starter, $001011$ indicates $011$ (the second in each pair terminates the current string) $\endgroup$ – Thinh D. Nguyen Oct 18 '18 at 7:21
  • $\begingroup$ Note that PDA is only one-direction less from being Turing-complete. $\endgroup$ – Thinh D. Nguyen Oct 18 '18 at 7:22
  • $\begingroup$ I don't understand what symbol doubling is. Could you please explain more? $\endgroup$ – xskxzr Oct 18 '18 at 9:31
  • $\begingroup$ @xskxzr I guess it means duplicating each symbol of the alphabet, e.g. $x=abcde$ to $x'=aabbccddee$. $\endgroup$ – chi Oct 18 '18 at 12:51
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I just realize that symbol doubling like in my question can still be pumped to contradiction. $\endgroup$ – Thinh D. Nguyen Oct 18 '18 at 14:31

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.