Prove that if C is a regular language, then the language $\{x x^R : x\in C\}$ is context-free

Question

Let $C$ be a regular language. Prove that the language $D = \{x x^R : x\in C\}$ is context-free.

It's clearly important that $C$ is regular; if the hypothesis were weakened to C being context-free, then we would have the counterexample $C = \{0^n 1^n : n\ge 0\}, D = \{0^n 1^{2n} 0^n:n\ge0\},$ which isn't context-free.

Assume $G_C$ is a context-free grammar for $C$ in Chomsky normal form. I don't think that just replacing every rule of the form $X\mapsto YZ$ in $G_C$ with $X\mapsto YZZY$ will produce the required language; rather it likely produces something like $\{x y^R :x,y \in C\} = C\cap C^R,$ which is clearly regular.

Maybe some closure properties might be useful? For instance, if $A$ is a context free language and $B$ is a regular language, then $A\cap B$ is context free. I know $CC$ is a regular language, and I know that the set of all palindromes of a regular language is a context-free language. But I don't think $D$ is the set of all palindromes of $CC$.

Answer 1

Recall that every finite state automaton can be changed into a rightlinear grammar which has productions like $X\to aY $ and $X\to \varepsilon$.

Your language can be generated using the same technique, but with linear productions which have the form $X\to aYa $ or $X\to \varepsilon$.