3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Hint: Mix2 is also called shuffle. See here for Mix1. $\endgroup$ – Raphael May 19 '15 at 14:01
  • $\begingroup$ @Raphael According to the reference given in your comment, it is $Mix_1$ that is called $shuffle$. $\endgroup$ – babou May 19 '15 at 19:43
  • 2
    $\begingroup$ Both $Mix_i$ operations actually extend to closure of any family of language that is a trio when combined with a regular set. So, for example, if $L_1$ is CF, and $L_2$ regular (or the converse), $Mix_i(L_1,L_2)$ is CF. The case of $Mix_1$ is quite similar to this question which also has a proof by closure properties, which can be reused here: Proving regular languages are closed under a form of interleaving. $\endgroup$ – babou May 19 '15 at 22:46
  • $\begingroup$ @babou That question used that word. Nevertheless, I know the term defined as Mix2; cf here. Mix1 is apparently also called perfect shuffle. $\endgroup$ – Raphael May 20 '15 at 7:35
  • $\begingroup$ @Raphael Indeed there is a question about perfect shuffle, but they did not say what unperfect shuffle is. Then I found another paper that was unprecise as it forgot to state whether the $u_i$ and $v_i$ were strings or single symbols (at least in the abstract). $\endgroup$ – babou May 20 '15 at 9:59
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Browsing the book of Hopcroft and Ullman (1979 edition) I see that shuffle is actually defined using these morphisms, except that letters $a, \bar a$ are used instead of $(a,1), (a,2)$. (Exercise 6.6, page 143). Also considered are the shuffle of two context-free languages, and the shuffle of one regular and one CFL. $\endgroup$ – Hendrik Jan May 26 '15 at 9:19
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I am still not sure how to bring your algorithm into practice (DFA construction) $\endgroup$ – Elimination May 19 '15 at 13:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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