[Solved]: Show that regular languages are closed under Mix operations

Problem Detail: 

Let $L_1, L_2$, two regular languages and the operations:

$$Mix_1(L_1, L_2) =\{ a_1b_1a_2b_2\ldots a_nb_n | n\ge 0 \land a_1,a_2,\ldots ,a_n,b_1,b_2,\ldots ,b_n\in\Sigma\\ \land a_1a_2\ldots a_n\in L_1 , b_1b_2\ldots b_n\in L_2\}$$

$$Mix_2(L_1, L_2) = \{ x_1y_1x_2y_2\ldots x_ny_n | n\ge 0 \land x_1,x_2,\ldots,x_n,y_1,y_2,\ldots,y_n\in\Sigma^* , x_1x_2\ldots x_n\in L_1 \land y_1y_2\ldots y_n\in L_2\}$$

Prove that regular languages are closed under $Mix_1$ and $Mix_2$ operations.

So for the first operation:
Let $D_1, D_2$, two DFA's accepting $L_1, L_2$, respectively. We define $D = (Q,\Sigma, \delta, q_0, F)$.

Where $Q = Q_1 \cup Q_2$. The transition function, $\delta$ will behave as $\delta_1$ and $\delta_2$. But in addition, Let's define $n = \left|\Sigma\right|$, then we make $n$ transitions from every $q_i\in Q_1$ to $q_j\in Q_2$ (and vice versa) for every $\sigma \in \Sigma$.

So it's pretty easy to see that $D$ accepts $Mix_1(L_1, L_2)$.

Question:
How can I show that regular languages are closed under $Mix_2$?

Asked By : Elimination

Answered By : Hendrik Jan

Take any string over the alphabet $\Sigma$. Colour some of the letters red and the remaining letters green. Accept the original string if the red letters form a string in $L_1$ and the green ones are in $L_2$.

More technically, regular languages are closed onder intersection and under (inverse) homomorpisms.

Let $\Gamma = \Sigma \times \{1,2\}$ be an alphabet with colours.

Define the homomorphisms $h_i:\Gamma^* \to\Sigma^*$, $i=1,2$ by $h_i(a,i) = a$ and $h_i(a,j) = \varepsilon$ for $i\neq j$. These keep only letters of their assigned colour, whereas their inverses colour the letters into that asigned colour while inserting arbitrary letters of the other colour.

Finally let $g:\Gamma^* \to\Sigma^*$ be the morphism $g(a,i) = a$ (which removes the colour).

Then $Mix_2(L_1,L_2) = g(\; h_1^{-1}(L_1) \cap h_2^{-1}(L_2) \;)$.

PS. Let $R_{12}$ be the regular language $[(\Sigma\times \{1\})(\Sigma\times \{2\})]^*$. Then $Mix_1(L_1,L_2) = g(\; h_1^{-1}(L_1) \cap h_2^{-1}(L_2) \cap R_{12} \;)$.

Just for fun, $L_1 \cdot L_2 = g(\; h_1^{-1}(L_1) \cap h_2^{-1}(L_2) \cap (\Sigma\times \{1\})^*(\Sigma\times \{2\})^* \;)$. Regular languages are closed under concatenation :)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42751