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...$
- $Q = Q_1 \cup Q_2$ ($\cup Q_1 \cup Q_2...?$ but it remains the same isn't it ?)
- $q_0=q_1$
- $F=F_1 \cap F_2$ as far as we have to have words from both $L_1$ and $L_2$.
- $\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$.