0 votes

Let $L_1$ be recursive and $L_2$ recursively enumerable. Show that $L_2-L_1$ is necessarily recursively enumerable.

1 vote

Best answer

$L_2 - L_1 = L_2 \cap {L_1}^c$

Now, complement of a recursive language is always recursive - so ${L_1}^c$ is recursive and hence recursively enumerable too.

Intersection of two recursively enumerable languages always gives a recursively enumerable language (Recursively Enumerable set is closed under union and intersection but not under complement).

So, $L_2 - L_1$ is guaranteed to be recursively enumerable.

Now, complement of a recursive language is always recursive - so ${L_1}^c$ is recursive and hence recursively enumerable too.

Intersection of two recursively enumerable languages always gives a recursively enumerable language (Recursively Enumerable set is closed under union and intersection but not under complement).

So, $L_2 - L_1$ is guaranteed to be recursively enumerable.