patternMinor
Are recursively enumerable languages closed under shuffle?
Viewed 0 times
arelanguagesclosedrecursivelyenumerableundershuffle
Problem
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 ?
$$ \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 ?
Solution
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?
Context
StackExchange Computer Science Q#76265, answer score: 2
Revisions (0)
No revisions yet.