Let be two languages $L_1,L_2$ we define the operation full-shuffle as $S(L_1,L_2)=\{w \mid w=w_1w_2...w_k\}$ such that $w_1,w_3,...\in L_1$ and $w_2,w_4...\in L_2$. In other words, the language $L$ only contains words that we can build from a word $L_1$ followed by a word from $L_2$, followed by a word from $L_1$, followed by a word from $L_2$, and so on...

How can I show that regular languages are closed by this operation ?

I have some difficulties to imagine the formalize automata resulting from this.

I did the following from p49, in Introduction to theory of computation from A. Meheshwari and M. Smid.

Let $M_1=(Q_1,\Sigma,\delta_1,q_1,F_1)$ be an NFA such that $A_1=L(M_1)$ and $M_2=(Q_2,\Sigma,\delta_2,q_2,F_2)$ be an NFA such that $A_2=L(M_2)$. We will construct an NFA $M=(Q,\Sigma,\delta,q_0,F)$ such that $L(M)=A_1A_2A_1A_2A_1...$

  1. $Q = Q_1 \cup Q_2$ ($\cup Q_1 \cup Q_2...?$ but it remains the same isn't it ?)
  2. $q_0=q_1$
  3. $F=F_1 \cap F_2$ as far as we have to have words from both $L_1$ and $L_2$.
  4. $\delta : Q\times\Sigma_\epsilon \rightarrow P(Q)$ is defined as folows :

$$\delta(r,a)=\begin{cases} \delta_1(r,a)\mbox{ if $r\in Q_1$}\\ \delta_2(r,a)\mbox{ if $r\in Q_2$}\\ \end{cases}$$

I'm new to this kind of proof and I'm not sure about it.


Well, you are missing the crucial parts. First of all, the set of accepting states should be $F_1 \cup F_2$, not the intersection. The idea is that we start in $M_1$, and when we have accepted a word $w_1$ in $M_1$, then we non-deterministically choose between either stopping there, or continue reading a word $w_2$ which should be in $M_2$. Hence you must add transitions $$\delta(r,a) = \begin{cases} \delta_2(r,a) \cup \{q_1\} \text{ if } r \in F_2 \text{ and } a = \varepsilon \\ \delta_1(r,a) \cup \{q_2\} \text{ if } r \in F_1 \text{ and } a = \varepsilon\end{cases}$$ that can take you from an accept state in one of the automata to the start state in the other. This way, you can "shuffle" back and forth between $M_1$ and $M_2$.


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.