Show that regular languages are closed under Mix operations

Question

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$?

Answer 1

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 :)

Answer 2

The solution you give for $Mix_1$ doesn't seem quite right - consider the simple case $\Sigma=\{a\}$ and $L_1=L_2=\{\epsilon\}$, where $\epsilon$ is the empty word; obviously in this case, $Mix_1(L_1,L_2)$ should also be $\{\epsilon\}$. The minimal DFA for this language is $(\{q_0,q_1\},\Sigma,\delta,q_0,\{q_0\})$ with $\delta(q_0,a)=\delta(q_1,a)=q_1$. Your construction for $Mix_1$ gives an NFA with set of states $\{q_{0,1},q_{0,2},q_{1,1},q_{1,2}\}$, where $q_{0,1},q_{0,2}$ are both initial and accepting, with set of transitions $\{(q_{i,j},a,q_{1,j})\ |\ i\in\{0,1\},j\in\{1,2\}\}\cup\{(q_{i,1},a,q_{j,2}),(q_{i,2},a,q_{j,1})\ |\ i,j\in\{0,1\}\}$; this will accept all $w\in\Sigma^*$.

In order to solve this problem, both for $Mix_1$ and $Mix_2$, the automaton you want needs to do the following:

• keep track of the state of a DFA $A_1$ for $L_1$ while parsing one subset of the letters in the input,
• keep track of the state of a DFA $A_2$ for $L_2$ while parsing the remaining letters in the input,
• alternate between progressing in $A_1$ and $A_2$,
• accept when the last step was in $A_2$ and both $A_1,A_2$ are in an accepting state.

The only difference between $Mix_1$ and $Mix_2$ in this regard is when to alternate (for $Mix_1$: after each letter, for $Mix_2$: whenever you want).

In order to keep track of the necessary information, the states should be of the form $(q_1,q_2,i)\in Q_1\times Q_2\times\{1,2\}$, where $q_j$ represents the current state of $A_j (j=1,2)$, and $i$ indicates in which automaton we will next progress. The initial state is $(q_{01},q_{02},1)$, representing the fact that each $A_j$ is in its initial state $q_{0j}$ and we want to first progress in $A_1$. The accepting states are those $(q_1,q_2,1)$ with $q_1\in F_1$ and $q_2\in F_2$, i.e. both $A_j$ accepting.

This leaves the transition relation. For $Mix_1$ this involves taking one step in component $i$ and then toggling $i$ (this is also the reason for requiring $i=1$ in the accepting states, since the last step should be in $A_2$). For $Mix_2$, you can either toggle $i$ or take a step in component $i$ (note that this given an NFA, i.e. you still need to determinize).

Answer 3

Hint: This is very similar to $Mix_1$, only you don't know when to jump from a part of the first word to a part of the second word. Use non-determinism to help you.