3
$\begingroup$

The operation of shuffle takes two words and merges their symbols, keeping the symbols of each of the strings in the right order. It can be recursively defined by $x \parallel \varepsilon = \varepsilon \parallel x = x$ and $ax \parallel by = a (x \parallel by) \cup b (ax \parallel y)$. Here $a,b\in \Sigma$ and $x,y\in \Sigma^*$. For languages $K\parallel L = \bigcup_{x\in K, y\in L} x\parallel y$.

It is known that the context-free languages are not closed under shuffle. An interesting question is raised in a recent arxiv overview paper Decision Problems on Copying and Shuffling 2302.06248 by Halava etal. Do we need more than two symbols for a counter example for shuffling two context-free languages?

Problem 6. Give an example of two context-free languages $L_1, L_2 \subseteq \{ a, b \}^*$ such that $L_1 \parallel L_2$ is not context-free.

$\endgroup$
1
  • $\begingroup$ The current version of the paper quoted and linked above mentions the example from the accepted answer. Example 3, page 14. $\endgroup$ Commented Nov 25, 2023 at 0:15

1 Answer 1

5
+100
$\begingroup$

Two letters should be sufficient as the following example shows: let $L_1=\{a^nba^n\mid n\geq1\}$ and $L_2=\{b^nab^n\mid n\geq1\}$. Then we have $$(L_1\|L_2)\cap a^*b^*a^*b^*=\{a^mb^{n+1}a^{m+1}b^n\mid m,n\geq1\}\,.$$ This equation holds, since we can only map the letters of a word from $L_1\subseteq a^*ba^*$ to the first three blocks of $a^*b^*a^*b^*$ and, similarly, the letters of a word from $L_2\subseteq b^*ab^*$ to the last three blocks.

The right-hand side of this equation is not context-free. Since the intersection of a context-free language with a regular language always is context-free, the language $L_1\|L_2$ cannot be context-free.

$\endgroup$
1
  • $\begingroup$ Well, that is fun! $\endgroup$ Commented Apr 11, 2023 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.