Given a language $L$ over $\Sigma=\{a,b\}$ let us define $L'=\{uv:u\in L \; \land v \in L^R \; \land |u|=|v|\}.$
Prove: if $L$ is regular, then $L'$ is a context free language.
*Note: If $L$ is regular then $L^R= \{w : w^R \in L\}$ is also regular
I know how to solve it by building a push down automaton and proving it acceps $L′$, but I'm trying to solve it by using closure properties of context free languages (e.g closure under homomorphism, intersection with a regular languae, etc.) but I couldn't think of such solution. Any ideas?
I claim that, more generally, if $R$ and $S$ are regular languages of $A^*$, then the language $$ L = \{uv \mid u \in R, v \in S, |u| = |v| \} $$ is context-free.
Proof. Let $\bar A$ be a disjoint copy of $A$ and let $B = A \cup \bar A$. Let $\pi:B^* \to \{a, \bar a\}^*$ be the monoid morphism defined by $\pi(c) = a$ and $\pi(\bar c) = \bar a$ for every letter $c \in A$. Since the language $L_0 = \{a^n \bar a^n \mid n \geqslant 0 \}$ is context-free, so is the language $$ L_1 = \pi^{-1}(L_0) = \{uv \mid u \in A^*, v \in {\bar A}^*, |u| = |v| \} $$ Let $\bar S$ be the copy of $S$ in ${\bar A}^*$. Since the language $R\bar S$ is regular in $B^*$, then the language $$ L_2 = L_1 \cap R\bar S = \{uv \mid u \in R, v \in \bar S, |u| = |v| \} $$ is context-free. Now, let $\gamma: B^* \to A^*$ be the monoid morphism "which deletes the bars", that is $\gamma(a) = \gamma(\bar a) = a$ for every $a \in A$. It remains to observe that $L = \gamma(L_2)$ to conclude that $L$ is context-free.