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.

  • 1
    $\begingroup$ Sounds good. Did you try it? Maybe try using the DFA for $R^R$ on the right-hand side $\endgroup$
    – rici
    Commented Jun 17, 2022 at 14:34
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Jun 17, 2022 at 19:32

1 Answer 1


Your operation is very general, and in its generality your conjecture is not true.

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$.


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.