2
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .