1
$\begingroup$

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??

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .