# Proving $L'=\{uv : u \in L \; \land v \in L^R \; \land |u|=|v|\}$ is a CFL with closure properties [duplicate]

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.

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?

• You can also easily prove this using context-free grammars. – Yuval Filmus May 26 '18 at 12:51

Let $\tilde\Sigma = \{\tilde a,\tilde b\}$. It is well-known that the language $X = \{a^n b^n : n \geq 0\}$ is context-free. Let $h \colon \Sigma \cup \tilde\Sigma \to \Sigma$ be the homomorphism defined by $h(a) = h(b) = a$ and $h(\tilde a) = h(\tilde b) = b$. The following language is context-free: $$h^{-1}(X) = \{uv : u \in \Sigma^*, v \in \tilde\Sigma^*, |u| = |v| \}.$$ Let $t\colon \Sigma \to \tilde\Sigma$ be the homomorphism defined by $t(a) = \tilde a$, $t(b) = \tilde b$. The following language is regular: $$Lt(L)^R = \{ uv : u \in L, v \in t(L)^R \}.$$ Since the context-free languages are closed under regular intersection, it follows that the following language is context-free: $$h^{-1}(X) \cap Lt(L)^R = \{ uv : u \in L, v \in t(L)^R, |u| = |v| \}.$$ Finally, let $s\colon \Sigma \cup \tilde\Sigma \to \Sigma$ be the homomorphism defined by $s(a) = s(\tilde a) = a$, $s(b) = s(\tilde b) = b$. The following language is context-free: $$s(h^{-1}(X) \cap Lt(L)^R) = \{ uv : u \in L, v \in L^R, |u| = |v| \}.$$ This is the language you're interested in.
Here is another solution, using context-free grammars. Let $\langle Q, \Sigma, q_0, \delta, F \rangle$ be an NFA for $L$, where $\Sigma = \{a,b\}$. We construct a context-free grammar whose non-terminals are $Q \times Q$. The starting symbol is $(q_0,q_0)$. For every $q_1,q_2 \in Q$ and $\sigma_1,\sigma_2 \in \Sigma$ we have the production $$(q_1,q_2) \to \sigma_1 (\delta(q_1,\sigma_1),\delta(q_2,\sigma_2)) \sigma_2.$$ For every $f_1,f_2 \in F$, we have the production $$(f_1,f_2) \to \epsilon.$$ A simple induction shows that for all $q_1,q_2$, we have $$(q_1,q_2) \Rightarrow^* w_1 (p_1,p_2) w_2$$ if and only if $p_1 = \delta(q_1,w_1)$, $p_2 = \delta(q_2,w_2^R)$, and $|w_1| = |w_2|$. Any word produced by the grammar must be produced via a derivation $$(q_0,q_0) \Rightarrow^* w_1 (f_1,f_2) w_2 \Rightarrow w_1w_2,$$ where $f_1,f_2 \in F$. From here it is easy to check that $w_1 \in L$, $w_2 \in L^R$, and $|w_1| = |w_2|$. The converse is also easy to check. Therefore this grammar generates $L'$.