Show that the class of regular languages is closed under shuffle

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.

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?

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$

StackExchange Computer Science Q#70408, answer score: 3