2
$\begingroup$

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?

$\endgroup$

marked as duplicate by Evil, Juho, Apass.Jack, xskxzr, Thinh D. Nguyen Oct 20 '18 at 1:02

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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