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
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.