# Prove or disprove that $\{xc o(x) :x \in A\}$ is context-free, where A is a regular language

Suppose o is a map on strings to strings. For every language R, we let $$o(R) := \{o(x) : x \in R\}$$. If o(R) is a regular language for every regular language R, then prove or disprove that the language $$\{xc o(x) :x \in A\}$$ is context-free, where A is a regular language and c is a symbol not in the alphabet of A, $$\Sigma$$.

The claim seems to hold when o is the reverse of a string, or the bitwise negation of it. I think a useful idea is to modify the rules for the CFG for A that are of the form $$X\rightarrow aY$$ for some alphabet element a and variables X and Y. So it might be useful to define Q variables in the new context free grammar, one for each state in a DFA recognizing A.

• Sounds good. Did you try it? Maybe try using the DFA for $R^R$ on the right-hand side
– rici
Jun 17 at 14:34
• Please indicate where you encountered this task and credit the source. We require you to credit the source of all copied material (as I have explained before): cs.stackexchange.com/help/referencing.
– D.W.
Jun 17 at 19:32

For instance take for $$o$$ the identity, then we get the simple example $$o(\{a,b\}^*) = \{wcw\mid w\in \{a,b\}^*\}$$ which is not context-free.
Your examples show that a better conjecture would be that instead $$\{ x c\, o(x^R)\mid x\in A\}$$ is context-free, where the second copy $$x$$ is reversed. In that case for the identity, $$\{ wcw^R \mid \dots\}$$ is nicely context-free for regular $$A$$.
But your statement is too general, as in that case we can take $$o$$ itself to be the mirror image of a string, and we are in trouble again.
The following general statement holds: if $$o$$ is performed by a finite state transducer, a finite state automaton with output, then $$\{ x c\, o(x^R)\mid x\in A\}$$ is context-free, for regular $$A$$.