# How to show that context-free languages are closed by the full-shuffle operation?

Let be the full-shuffle operation, $S(L_1,L_2)=\{w|w=w_1w_2...w_k\mbox{ such that$w_{2k+1}\in L_1$and$w_{2k}\in L_2$,$k\in\mathbb{N}$}\}$. That is to say the language $L$ that contains the words which we can build from a word from $L_1$, followed by a word from $L_2$, followed by a word from $L_1$, etc...

### My attempt

Let be two grammars which variables are disjoint and whichi initial variables are $S_1$ and $S_2$. We take the grammar which have a new initial variable $S$.

$$S\rightarrow \varepsilon | S_1|S_2$$ $$S_1\rightarrow DS_1$$ $$S_2\rightarrow DS_2$$ $$DS_1\rightarrow DS_1S_2$$ $$DS_2\rightarrow DS_2S_1$$

Just like in your previous question, there is a small ambiguity in the definition since you do not specify whether $k$ should be even. Anyway, if you assume that $k$ is even, then $S(L_1,L_2) = (L_1L_2)^*$ and if there is no restriction on $k$, then $S(L_1,L_2) = (L_1L_2)^* \cup (L_1L_2)^*L_1$.
In both cases, if $L_1$ and $L_2$ are regular, then $S(L_1,L_2)$ is regular (which answers your previous question, and if $L_1$ and $L_2$ are context-free, then $S(L_1,L_2)$ is context-free, since regular [respectively context-free] languages are closed under union, product and star.
• Thank you for your answer ! Yet, even if I understand what you wrote. We use to use a system with arrow to display these grammar. For instance : \begin{align*} P &→ N P_v\\ P &→ P \mbox{ and } P\\ P_v&→ V\\ P_V&→ V N\\ N& → Francois\\ N&→ Nicolas\\ N&→ Marine\\ V&→ loves\\ V&→ hates\\ V&→ run\\ \end{align*} It allows to represent phrases like this : $P$ is a full sentence, $P_v$ is the verbal part. $N$ is the noun and $V$ is the verb. For our case, would it be : \begin{align} S\rightarrow(L_1&L_2)^*\bigcup(L_1L_2)^*L_1 \end{align} – ThePassenger Apr 24 '17 at 10:00
• And $k\in \mathbb{N}$ only, no other restrictions... – ThePassenger Apr 24 '17 at 10:01