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.

$\endgroup$
7
  • $\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$ Oct 18, 2018 at 7:19
  • $\begingroup$ Take symbol doubling as a starter, $001011$ indicates $011$ (the second in each pair terminates the current string) $\endgroup$ Oct 18, 2018 at 7:21
  • $\begingroup$ Note that PDA is only one-direction less from being Turing-complete. $\endgroup$ Oct 18, 2018 at 7:22
  • $\begingroup$ I don't understand what symbol doubling is. Could you please explain more? $\endgroup$
    – xskxzr
    Oct 18, 2018 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, 2018 at 12:51

1 Answer 1

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.

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

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.