For languages $A$ and $B$ over the same alphabet $\Sigma$, the perfect shuffle of $A$ and $B$ is:

$$S(A, B) = \setbuilder{x}{x = a_1 b_1 \dots a_k b_k \text{ with } a_i, b_i \in \Sigma, a_1 \dots a_k \in A, b_1 \dots b_k \in B}$$

We show that for regular languages $A$ and $B$, $S(A, B)$ is also regular.

---

Let $M_A = (Q_A, \Sigma, \delta_A, q_{0A}, F_A)$ and $M_B = (Q_B, \Sigma, \delta_B, q_{0B}, F_B)$ be DFAs that accept $A$ and $B$, respectively. We construct a machine $M_S = (Q_S, \Sigma, \delta_S, q_{0S}, F_S)$ that accepts $S(A, B)$.

Let $Q_S = \set{p_A, p_B} \times Q_A \times Q_B$. Take $q_{0S} = (p_A, q_{0A}, q_{0B})$. Take $F_S = \set{p_A, p_B} \times F_A \times F_B$.

Finally, define:

$$\delta_S((p, q_1, q_2), x) = \left\{ \begin{array}{lr} (p_B, \delta_A(x), q_2) & p = p_A \\ (p_A, q_1, \delta_B(x)) & p = p_B \end{array} \right.$$

So $M_S$ alternates between advancing a copy of machine $M_A$ and $M_B$, keeping track of which machine to advance with $p_A$ and $p_B$. So $M_S$ accepts $S(A, B)$, and $S(A, B)$ is regular.