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

How to show that context-free languages are closed by this operation ?

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.

  • $\begingroup$ 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} $\endgroup$ – ThePassenger Apr 24 '17 at 10:00
  • $\begingroup$ And $k\in \mathbb{N}$ only, no other restrictions... $\endgroup$ – ThePassenger Apr 24 '17 at 10:01

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.