Let $C = shuffle(A, B)$ denote the shuffle $C$ of two languages $A$ and $B$, it consists of all strings $w$ of the form $w = a_1b_1a_2b_2....a_kb_k$, for $k > 0$, with $a_1a_2 ··· a_k \in A$ and $b_1b_2 ··· b_k \in B$. Show that if A and B are regular then so is $C = shuffle(A, B).$

  • 2
    $\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? We want to help you with your specific problems, not just do your (home-)work. However, as it is we don't know what this problem is and thus how to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ Commented Aug 15, 2014 at 16:58
  • 1
    $\begingroup$ Ok, this is not at all a homework problem. I was trying to make connection with construction of concatenation property og regular languages. I was thinking of doing something like defining new states as $Q_1 \times Q_2$ and new transition function $f((x,y),a)=(f_1(x,a),y)\cup (x,f_2(y,a))$. but i don't think its working $\endgroup$
    – James Yang
    Commented Aug 15, 2014 at 17:05
  • $\begingroup$ Hmm, this k > 0 condition is quite crucial here. $\endgroup$ Commented Aug 15, 2014 at 18:45
  • $\begingroup$ @JamesYang I've added an answer that I think correctly interprets your problem and which approaches things like you're trying to: by constructing an automaton. Notice the definition $\delta''$ of the transition function, although the definition of $Q''$ might be even more instructive. $\endgroup$
    – Patrick87
    Commented Aug 15, 2014 at 18:56
  • 1
    $\begingroup$ I second @ZeroUltimax's comment. This seems like pretty basic problem; just dumping the it here is not the most nice thing to do. It makes you look as if you are not ready to spend anytime yourself before asking others to do so. One note about terminology: the term "shuffle" is typically associated with a different operation. $\endgroup$
    – Raphael
    Commented Aug 15, 2014 at 21:56

1 Answer 1


Suppose $A$ and $B$ are regular. Let $M_A$ and $M_B$ be DFAs for $A$ and $B$, respectively. We know $M_A$ and $M_B$ exists since every regular language is accepted by some $DFA$.

Let $M_A = (\Sigma, Q, q_0, A, \delta)$ and $M_B = (\Sigma', Q', q_0', A', \delta')$.

We define $M_C = (\Sigma'', Q'', q_0'', A'', \delta'')$ such that $L(M_C) = shuffle(A,B)$.

First, let $\Sigma'' = \Sigma \cup \Sigma'$.

Next, choose $Q'' = \{0, 1\} \times Q \times Q'$.

Now, choose $A'' = \{(0, q, q') \mid q \in A, q' \in A' \}$.

Let $q_0'' = (0, q_0, q_0')$.

Now the fun part: what is the transition function? Here's what it's going to do:

  1. If $q'' = (0, q, q')$, then $\delta''(\sigma, q'') = (1, \delta(\sigma, q), q')$ if $\delta(\sigma, q)$ is defined, or undefined otherwise (we're going to get an NFA, but that's OK).

  2. If $q'' = (1, q, q')$, then $\delta''(\sigma, q'') = (0, q, \delta'(\sigma, q'))$ if $\delta'(\sigma, q')$ is defined, or undefined otherwise (again, we're going to get an NFA, but that's good enough for establishing regularity).

Basically, we're using the state to encode whether the last symbol we saw was from a word in $A$ or from a word in $B$. We can only accept if the last symbol we saw was from a word in $B$, hence our set of accepting states requiring that we have 0 for the parity. Furthermore, we can only accept if we've seen a complete word from both $A$ and $B$, which is why we require the other components to be accepting states in their respective automata.

You can think of this as two simultaneous DFAs produced from the Cartesian-Product construction for the intersection of the languages. After evaluating each step, we jump to the other machine. The first machine accepts input corresponding to the language $A$, and the second machine accepts input corresponding to the language $B$.

The full proof that this construction yields a correct automaton is left as an exercise.

Note that this construction technically allows $k = 0$, which is not allowed by the language in the question. To complete the exercise, argue that the NFA obtained above can be converted to a DFA by a standard construction, and that intersecting the resulting DFA with a DFA for the language of positive-length strings gives a DFA for the desired language.

  • $\begingroup$ Wait, I can't understand why its working. Its working if $a_i,b_i$'s were given as symbols (path is going like a alternating sequence). If not then dunno why can;t be convinced $\endgroup$
    – James Yang
    Commented Aug 15, 2014 at 20:08
  • $\begingroup$ like I;m saying let $a_1=f_1f_2$. Starting from initial state after reading $f_1$ it'll go to $(1,q_1,q_0')$ but then after reading $f_2$ where will it go ? $f_2$ doesn't have access on $q_0'$ $\endgroup$
    – James Yang
    Commented Aug 15, 2014 at 20:16
  • $\begingroup$ Well, I think this should work. First remove those $\{0,1\}$. Now define start state as $(q_1,q_2,0)$ but define other states as $(a,b)|a\in Q_1,b\in Q_2$ and accepting state $F_1 \times F_2$. Now define $\delta$ for non starting states as follows $\delta((a,b),x)=(\delta_1(a,x),b)\cup (a,\delta_2(b,x)$. Now for starting state define it, $\delta((q_1,q_2,0),x)=(\delta_1(q_1,x),q_2)$ .. this'll prove any $a_1b_1.....a_kb_k$ will be accepted but not any of $b_1a_1....b_ka_k$ $\endgroup$
    – James Yang
    Commented Aug 15, 2014 at 20:35
  • $\begingroup$ @JamesYang Let $a = 123$ and $b = xyz$, with $a \in A$ and $b \in B$. Is your language such that $1x2y3z = c \in C = shuffle(A, B)$? If so, that's what the automaton described here should accept. In your example, after reading $f_2$, it should go to $(0, q_1, q_1')$. This assumes when you write $a_1 = f_1f_2$ you mean $a_1b_1 = f_1f_2$. The machine that expects $B$-type input "crashes" (in the nondeterministic sense) if it gets something it can't handle. Otherwise, I'm not sure I understand what you're really asking. $\endgroup$
    – Patrick87
    Commented Aug 15, 2014 at 21:02
  • $\begingroup$ I'm saying is, suppose $a_1=f_1f_2\in A,b_1=g_1g_2\in B$ where $f_1,f_2,g_1,g_2$ are symbols, $a_1,b_1$ are strings So, $\widehat{\delta_{1}(a_1,q_0)}\in F_1,\widehat{\delta_{2}(b_1,q'_0)}\in F_2$. Now after reading $a_1b_1$ we go to $(0,\widehat{\delta_1(f_1g_1,q_0)},\widehat{\delta_2(f_2g_2,q'0)})$. So to fall in accept state we must have $\widehat{\delta_1(f_1g_1,q_0)}\in F_1$ ? $\endgroup$
    – James Yang
    Commented Aug 16, 2014 at 3:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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