The Gateway to Computer Science Excellence
0 votes
Let $L_1$ be recursive and $L_2$ recursively enumerable. Show that $L_2-L_1$ is necessarily recursively enumerable.
in Computer Networks by Boss (11.6k points) | 23 views

2 Answers

+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.
by Veteran (431k points)
selected by
0 votes
  • Recursive is closed under complement.
  • Recursive ennum is closed under intersection .


by Boss (36.5k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,291 answers
104,902 users