Constructing a NFA for the following language

Question

For languages $ A$ and $B$, let the perfect shuffle of $A$ and $B$ be the language $\{w \mid w = a_1b_1 \dots a_kb_k, \text{ where } a_1 \dots a_k ∈ A \text{ and } b_1 \dots b_k ∈ B, \text{ each } a_i,b_i ∈ Σ\}$.

Prove that the perfect shuffle of $A$ and $B$ is regular.

We will create a NFA in the following manner:

So the latter is a part of NFA $A$. We will do the following for every transition of this type. We know that any state that recevies input maps other state. What we want is to stop at state $q_r$, read input from the language $B$ and return to the same state to read the next input. For that we will turn $q_r$ into a box that reads input from $B$.

The start state is the first state of $A$ and the accept states are all the accept states of $B$.

Answer 1

There are several ways to prove that the perfect shuffle of two regular languages is regular. Here's one.

We start with automata $M_a$ and $M_b$ for $A$ and $B$, respectively. To fix ideas, suppose they are DFAs. We first build a helper automaton $G$--technically known as a gadget--that constantly alternates between its two states $0$ and $1$. The purpose of this automaton is to keep track of whether we are reading an $a$ or a $b$. Its initial state is $0$,which is also its only final state.

We then combine the automata for $A$ and $B$ into one "product" automaton $P$, with a state $(s,t)$ for every $s$ in $M_a$ and each $t$ in $M_b$. The input alphabet of this product automaton is $\Sigma \times \{0,1\}$. That is, at every round, $P$ reads a letter of the input word, and also the state of $G$. If $G$ is in state $0$, $P$ changes only the first component of its state according to the transition relation of $M_a$, and otherwise it behaves like $M_b$, and changes only the second component of its state. Note that if $M_a$ and $M_b$ are deterministic, so is $P$.

Finally, we compose $P$ and $G$ to obtain $C$. Each state has now three components: one from $M_a$, one from $M_b$, and one from $G$. The initial state of $C$ is the state with three initial components and the final states are those made up of three accepting components. The transition relation of $C$ is defined in the natural way. It's not difficult to see that $C$ accepts the perfect shuffle of $A$ and $B$.

One does not need to introduce $G$, and can instead define $C$ directly, but the approach I've taken here is easier to describe without getting too mired into details. Another approach, which may appeal to those familiar with the closure properties of regular languges, is to define an automaton whose input language is $\Sigma \times \Sigma$ as intermediate step.