# Closure of regular languages to shuffle using closure operations

Given a language: $L = \{\; a_1b_1a_2b_2a_3b_3\dots a_nb_n \mid \forall i: a_i,b_i \in \Sigma, a_1\dots a_n \in L_1\ , b_1\dots b_n \in L_2 \;\}$

Also $L_1, L_2$ are regular languages.

Using closure only (homomorphism) prove that L is also regular language.

I think there can be a mapping $h\colon (L_1 \cup L_2) \to \Sigma$, then use $h^{-1}(\Sigma)$ in order to show regularity. I'm a bit stuck over here.

• A homomorphism is a mapping from an alphabet to strings, not from a language to an alphabet. – Yuval Filmus Jan 8 '17 at 20:11
• 1. Is $n$ fixed in advance? Or is it allowed to vary? 2. What does your notation mean? Do you mean that every word in $L$ is of length exactly $2$? Or is it length $2n$? – D.W. Jan 8 '17 at 20:55

The idea is to create two copies of the alphabet $\Sigma$, say $\Sigma_1,\Sigma_2$; each $\sigma \in \Sigma$ corresponds to $\sigma^{(i)} \in \Sigma_i$. You now show that the following languages are regular: \begin{align*} \tilde{L}_1 &= \{a_1^{(1)}b_1^{(2)}\ldots a_n^{(1)}b_n^{(2)} : a_1 \ldots a_n \in L_1 \}, \\ \tilde{L}_2 &= \{a_1^{(1)}b_1^{(2)}\ldots a_n^{(1)}b_n^{(2)} : b_1 \ldots b_n \in L_2 \}, \end{align*} where in both cases only some of the letters are constrained. Now take $\tilde{L}_1 \cap \tilde{L}_2$ and transform it to $L$.
• I thought of another solution, not sure if its also correct. I can probably have a mapping $h: \Sigma_1 \to \Sigma_1 \cup \Sigma_2$ such that $\forall i, h(a_i) = a_ib_i$ then given that $L_1$ is regular i can use homomorphism to prove $L$ regularity. – Joey Kaller Jan 8 '17 at 20:28