# Constructing a NFA for the following language

For languages $A$ and $B$, let the perfect shufﬂe 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$.

• Are the $a_i$ and $b_i$ supposed to be letters in languages $A$ and $B$ ($a_i,b_i\in \Sigma$ as you write) or words in languages $A$ and $B$ (so usually rather in $\Sigma^*$)? Feb 7 '17 at 7:55

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.

• Thank you somuch Fabio, I understand your idea of creating a helper automata to control the switching between automatas. I am just wondering if my approach is correct even-though it may look inefficient. Feb 8 '17 at 5:55
• At best, I can say I may have an idea of what you intend to do. Note that it's not enough for acceptance that the "b part" of a word (the even numbered letters of that word) be in B. I'm also not sure whether by the two strings of three states you mean just an example, or more. I believe there's at least the seed of a correct solution in that diagram, but from that to a correct solution, there's probably some distance yet to cover. Feb 8 '17 at 6:01
• Yes, we will do the above process every three states in a row to control the switching. Feb 8 '17 at 6:10
• The problem is that $a_z$, for example, may have multiple successors, and you need enough states to remember that. The problem is unavoidable and "going nondeterministic" doesn't solve it. The solution, more or less explicitly, needs some kind of product automaton. Feb 8 '17 at 6:14