USA: +1 (725) 712-1730 
Sign in
We define the SHUFFLE of two strings v, w elementof sigma* as: SHUFFLE(v, w) = {v_1 w_1 v_2 w_2 … v_k w_k|v = v_1 v_2 … v_k, w = w_1 w_2 … w_k, and for some k greaterthanorequalto 1, v_i, w_i elementof sigma*, 1 lessthanorequalto i lessthanorequalto k For example, 212ab1baa2b22 elementof SHUFFLE(abbaab, 2121222) Extend the definition of SHUFFLE to two languages L_1, L_2 subsetorequalto sigma* as follows: SHUFFLE(L_1, L_2_ = {w|w_1 elementof L_1, w_2 elementof L_2, w elementof SHUFFLE(w_1, w_2)} a) Is the SHUFFLE of two regular languages necessarily regular? b) Is the SHUFFLE of two decidable languages necessarily decidable?
Expert Answer
a)
If L1 and L2 are regular languages then Shuffle(L1, L2) is also regular.
Here L1 and L2 are regular. Hence there are two DFAs D1 and D2 which accepts L1 and L2.
We can create a NFA D that accepts shuffle(L1, L2) in following manner :
– In D, we need to keep track of one important matter : current status , i.e whether we are reading character for L1 or L2. It could be for any of it. so here we add non-determinism to guess whether current input symbol is from L1 or L2. i.e whether it is read in D1 or D2.
– after each input symbol we can consider one of the possibility.
– In the end if string is accepted by both D1 and D2 then we can say that the NFA accepts given input string.
Hence such NFA is possible for given language. So we can say that given language shuffle(L1, L2) is regular.
b)
Here L1 and L2 are decidable languages, hence there is some Turing machine M1 and M2 that accepts languages L1 and L2.
– We can create a TM(Non deterministic turing machine) M for Shuffle(L1, L2) in following manner :
– Here also at each input symbol we can onsider it to be from L1 or L2.
– After considering each possibility, at the end both M1 and M2 machine halts.
if M1 and M2 both halts at final state then we can say that given string is accepted by M.
Hence, there is a Non-deterministic turing machine M that accepts w if w is in language shuffle(L1, L2).
Note that turing machine M halts in any case.
so we can say that given language Shuffle(L1, L2) is decidable if L1 and L2 are decidable.
if you have any doubts then you can ask in comment section.
