Shuffle and Perfect Shuffle

These two problems from the book of Mike Sipser (1.41 and 1.42) need a little bit of discussion, for I guess these two are the most coveted problems in all university coursework. Question# 1.41 deals with shuffle and question# 1.42 is an extension of shuffle  called perfect shuffle. Let's look at the problem of perfect shuffle  first, then we can modify our answer for shuffle.  

For language $A$ and $B$, let the perfect shuffle of $A$ and $B$ be the language \[\{w|w=a_1b_1...a_kb_k. \textrm{ where }a_1...a_k \in A \textrm{ and } b_1...b_k \in B, \textrm{ each }a_i,b_i \in \Sigma\}\]. Show that the class of regular language is closed under perfect shuffle.

 This is a proof by construction. Let $M_A = (Q_A;\Sigma; \delta_A; q_A; F_A)$ and $M_B = (Q_B;\Sigma; \delta_B; q_B; F_B)$ be two DFAs that recognize $A$ and $B$, respectively. Here, we shall construct a DFA $M = (Q;\Sigma; \delta; q; F)$ that recognizes the perfect shuffle of $A$ and $B$. The construction proceeds as follows.

1. $Q=Q_A \textrm{ x }Q_B \textrm{ x }\{A,B\}$.
2. $q=(q_A,q_B,A)$.
3. $F=F_A \textrm{ x }F_B\textrm{ x }{A}$, as the next character to read should be in $M_A$. (The last character read was in $M_B$).
4. $\delta$ is defined as -
1. $\delta((x,y,A),a)=(\delta_A(x,a),y,B)$.
2. $\delta((x,y,B),b)=(x,\delta_B(y,a),A)$.

The construction of shuffle DFA is more or less the same, but with fewer restrictions. Let me state the question first.

For language $A$ and $B$, let the shuffle of $A$ and $B$ be the language \[\{w|w=a_1b_1...a_kb_k. \textrm{ where }a_1...a_k \in A \textrm{ and } b_1...b_k \in B, \textrm{ each }a_i,b_i \in \Sigma^*\}\]. Show that the class of regular language is closed under shuffle.

Now let's take a look at the construction. Again we are going to design a combined DFA with the same tuples as defined for the last problem.

1. $Q=Q_A \textrm{ x }Q_B \cup {q_0}$, $q_0$ defines the state when nothing is read.
2. $q=q_A$.
3. $F=F_A \textrm{ x }F_B \cup {q_0}$, as this DFA can accept the null string.
4. $\delta$ is defined as -
1. $\delta(q_0,\epsilon)=(q_A,q_B)$.
2. $(\delta_A(x,a),y) \in \delta((x,y),a)$.
3. $(x,\delta_B(y,a)) \in \delta((x,y),a)$.

I guess these two construction answer the problems satisfactorily. Thanks to Wing-Kai Hon of National Tsing Hua University for the discussion of the above problems.