= Solution
\b[Yes: <regular languages> are closed under the <shuffle of formal languages>.] The construction must allow letters common to both <alphabets> to be assigned to either input <word>.
Take complete <deterministic finite automata> $\mathcal A_i=(Q_i,\Sigma_i,\delta_i,s_i,F_i)$ recognizing $L_i$. Construct a <nondeterministic finite automaton> on $Q_1\times Q_2$ over $\Sigma=\Sigma_1\cup\Sigma_2$. Its initial state is $(s_1,s_2)$ and its accepting states form $F_1\times F_2$. On a letter $a$, its possible moves from $(p,q)$ are
$$
\begin{aligned}
(p,q)&\longrightarrow(\delta_1(p,a),q)&&\text{if }a\in\Sigma_1,\\
(p,q)&\longrightarrow(p,\delta_2(q,a))&&\text{if }a\in\Sigma_2.
\end{aligned}
$$
Both moves are allowed when $a$ belongs to both <alphabets>. They may coincide; that causes no difficulty.
For every run, record whether each move updated the first or the second coordinate. The letters assigned to each coordinate, in their original order, form two <words> $u_1,u_2$. The final coordinate states are exactly the states reached by reading $u_i$ in $\mathcal A_i$. Thus an accepting run expresses the input as an interleaving of a <word> of $L_1$ and a <word> of $L_2$.
Conversely, given such an interleaving, assign each input position to the <word> from which it came. The corresponding choices of transitions form a run ending in $F_1\times F_2$. This proves equality between the recognized <formal language> and the <shuffle of formal languages>, in both directions. No assumption of disjoint <alphabets> is needed. If one contributing <word> is the <empty word>, no move need update that coordinate; the initial pair is accepting exactly when both <empty words> are accepted.
Apply the <powerset construction> to this <nondeterministic finite automaton> to obtain a <deterministic finite automaton>. In particular,
$$
\boxed{L_1\oplus L_2\text{ is regular},\qquad \text{a recognizing DFA has at most }2^{|Q_1||Q_2|}\text{ states}.}
$$
Back to article page
