Prove claims about disjoint union and decidable/undecidable languages

1.1k Views Asked by At

Let $L\subseteq\Sigma^*$ decidable language and $A\subseteq\Sigma^*$.

Let $B=A\sqcup L$ (a disjoint union).

Prove:

$1$. $B\in RE \Rightarrow A\in RE$

$2$. $B\in R \Rightarrow A\in R$

Thanks!

1

There are 1 best solutions below

0
On BEST ANSWER

If $B = A \sqcup L$ then $A = B \cap \overline{L}$, where $\overline{L} = \Sigma^* \setminus L$. Note that $\overline{L}$ is decidable. The classes $R$ and $RE$ are closed under finite intersections (and unions also). Hence if $B \in RE$ (or $B \in R)$ then (since we also have $\overline{L} \in R \subset RE$) it holds that $A = B \cap \overline{L} \in RE$ (or $B \cap \overline{L} \in R$ respectively).