For languages A and B, let the shuffle of A and B be the language
$ \{w| w = a_1b_1···a_kb_k,$ where $a_1···a_k ∈ A$ and $b_1···b_k ∈ B,$ each$ a_i,b_i ∈ Σ^∗\}$.
Show that the class of regular languages is closed under shuffle.

Approach: If A and B are regular, then there exists an NFA R and T that recognizes them. I was thinking I could run R and T in parallel, so I would start running R by processing $a_1$ and then by using non-determinism, I would jump to the NFA T to process $b_1$. In this process I make sure that both NFAs aren't executed the original way because that would result in accepted strings that are not in the language, so I try to disconnect the edges in each NFA to jump to the other NFA and then disconnect again the edges of this NFA to come back to the previos NFA.. Is this process clear?

Here is the proof, but some lines are a bit unclear to me.enter image description here

I can't understand d)i. I don't understand how the transition function works. How does it detect whether we are at DFA A OR B?

  • $\begingroup$ Note that the proof seems to assume that $N$ should accept the empty string by making $q_0$ final. In my interpretation of shuffle $N$ can only accept the empty string if both $D_A$ and $D_B$ accept the empty string. It seems that $q_0$ can be avoided altogether by starting in state $(q_A,q_B)$. $\endgroup$ Commented Feb 17, 2017 at 16:08

1 Answer 1


Suppose, we have a simple string like $w = a_1b_1$ then what I understand you want to do is process $a_1$ in $D_A$ then jump to initial state of $D_B$ using $\epsilon$-transition and the process $b_1$ in $D_B$ but we don't know where $a_1$ ends and $b_1$ starts. So using non determinism we check all possibilities of where $a_i$ can end and $b_i$ can start.

  • To do that we start with a combined starting state $(q_A,q_B)$.
  • We have all the states possible by making $Q = Q_A \times Q_B$
  • Now we two kind of transitions from any state from $Q$ first we make transition in $D_A$ ignoring the transition in $D_B$ that way we can handle the case where the symbol is part of $a_i$. In a similar way we will add second kind of transitions assuming symbol is part of $b_i$.

Going this way there won't be any possibility left unchecked.

How does it detect whether we are at DFA A OR B?

we don't have a marker between $a_i$ and $b_i$ so we make 2 guess at every state. First, The symbol is part of $a_i$ or $b_i$ we are currently in and second, that the current symbol is first symbol of the next $b_i$ if we currently checking $a_i$ and next $a_{i+1}$ if currently checking $b_i$


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.