context-free shuffle for two-letter alphabets

Question

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.

Answer 1

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.