# Are recursively enumerable languages closed under shuffle?

For languages $L_1, L_2$ over some alphabet $\Sigma$, we define

$$\textit{Shuffle}(L_1, L_2) = \{a_1b_1a_2b_2 \cdots a_nb_n : n \geq 1 \wedge a_1, \ldots , a_n \in L_1 \setminus \{ \varepsilon \} \wedge b_1, \ldots , b_n \in L2 \setminus \{ \varepsilon\}\}$$

I think that RE are closed under shuffle, I tried to use the multitape TM model with 3 tapes, one for the input, one for the $a_1, \ldots , a_n \in L_1 \setminus \{ \varepsilon \}$, and the last one for $b_1, \ldots , b_n \in L_2 \setminus \{ \varepsilon \}$, but the problem is that $a_1, \ldots , a_n, b_1, . . . , b_n$ are words from the languages,not symbols, so we do not know when $a_1$ ends and $b_1$ begins, any suggestions for proving closure under shuffle ?

• Try the definition of RE via machines that enumerate all strings in a language. – Yuval Filmus Jun 3 '17 at 11:25
• It seems that it should solve the problem, according to the relation between enumerators and TM's I am thinking of using the enumerators of L1 and L2 to create another one for shuffle, but how can I do it if L1 and L2 can be infinite languages and n>=1, which means that there are words in the shuffle language that we can't write in the enumerator – user7370059 Jun 3 '17 at 14:03

## 1 Answer

Hint: A language is recursively enumerable if and only if it can be recognised by a nondeterministic Turing machine. Use this fact to build a nondeterministic recogniser for $\textsf{shuffle}(L_1,L_2)$ from the deterministic recognisers for $L_1$ and $L_2$. What is it, that one most use nondeterminism to guess?