For languages $A$ and $B$, let the perfect shuffle of $A$ and $B$ be the language $$L=\{w \ \mid \ w=a_1 b_1 \dots a_k b_k, \text{ where } a_1 \cdots a_k \in A \text{ and } b_1 \cdots b_k \in B, \text{ each } a_i, b_i \in \Sigma\}$$
Show that the class of regular languages is closed under perfect shuffle.
$$$$
I have done the following:
Let $M_A=(Q_A, \Sigma , \delta_A, q_A, F_A)$ the DFA that accepts the language $A$ and $M_B=(Q_B, \Sigma , \delta_B, q_B, F_B)$ the DFA that accepts the language $B$.
Let $M=(Q, \Sigma , \delta, q, F)$ the NFA that accepts the language $L$, with
$Q=Q_A \times Q_B$,
$\delta: (k_A, a_i) \mapsto k_B$, where $k_A, k_B$ states of the machine $M_A$ and $M_B$ resectively
$q=q_A$
$F=F_B$
Is this correct??
Best Answer
The way you have written it now is incorrect. Notice that you have said that the states of $M$ are given by $Q = Q_A \times Q_B$, so a state of $Q$ would have the form $(k_A,k_B)$, where $k_A \in Q_A$ and $k_B \in Q_B$.
This means that the transition function should be of the form $\delta : Q_A \times Q_B \times \Sigma \rightarrow Q_A \times Q_B$, whereas your current transition function is $\delta : Q_A \times \Sigma \rightarrow Q_B$. In fact, since you stated that you want an NFA, the transition function should be of the form $\delta: Q_A \times Q_B \times \Sigma \rightarrow \mathcal{P}(Q_A,Q_B)$. Similarly, both $q$ and $F$ must be pairs of states.