300 views

2 Answers

Best answer
1 votes
1 votes
$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.
selected by

Related questions

0 votes
0 votes
0 answers
2
0 votes
0 votes
1 answer
4