Problem Detail: I’m trying to find two languages, $L_1, L_2 in RE setminus R$, such that $L_1 cup L_2 in R$. I have already proved that if $L_1cap L_2 in R$ and $L_1 cup L_2 in R$, such $L_1, L_2$ don’t exist (because otherwise we’ll be able to construct a Turing Machine $M_1$ which will decide $L_1$, for instance). However, I cannot prove that it’s impossible in the case $L_1cap L_2 in RE setminus R$, and I can’t find such languages.
Asked By : Tomer
Answered By : Shaull
Take $L_1={0cdot x:xin Sigma^*}cup {1cdot x: xin A_{TM}}$ and $L_2={1cdot x:xin Sigma^*}cup {0cdot x: xin A_{TM}}$. Clearly both languages are in $REsetminus R$. However, their union contains ${0cdot x}cup {1cdot x}=Sigma^*setminus{epsilon}$, so their union is $Sigma^*$, and is therefore decidable.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/12252
