How to construct a DFA for this?

Question

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

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.