Undecidable language problems

37 Views Asked by At

Let $L_1$ and $L_2$ be two undecidable languages.

1) Is it possible that $L_1 - L_2$ is regular and $L_1 - L_2 \neq \emptyset$ ?

Well I know that if I let $L_1 = L_2$ then $L_1 - L_2 = \emptyset$ which is obviously regular. In the case of this question however, I cannot set $L_1 = L_2$ if the outcome is an empty set, which makes me wonder what would $L_1 - L_2$ actually look like if they were not equal to each other.

2) Is it possible that $L_1 \cup L_2$ is decidable and $L_1 \neq \neg L_2$ ?

This one is also tricky, since the obvious solution here would be to let $L_1 = \neg L_2 $.

Does anyone here have an idea as to how to finish my solutions here? I need to prove my solutions in both cases.