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

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

1 Answer

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