2
$\begingroup$

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

$\endgroup$
2

1 Answer 1

3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.