3
$\begingroup$

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 ?

Improve this question
$\endgroup$
2
  • $\begingroup$ Try the definition of RE via machines that enumerate all strings in a language. $\endgroup$
    – Yuval Filmus
    Jun 3, 2017 at 11:25
  • $\begingroup$ 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 $\endgroup$
    – user7370059
    Jun 3, 2017 at 14:03

1 Answer 1

Reset to default
2
$\begingroup$

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?

Improve this answer
$\endgroup$

Your Answer

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

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