The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+36 votes

Let $L_1$ be the recursive language. Let $L_2$ and $L_3$ be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

  1. $L_2 - L_1 \:\text{is recursively enumerable.}$
  2. $L_1 - L_3 \:\text{is recursively enumerable.}$
  3. $L_2 \cap L_3 \:\text{is recursively enumerable.}$
  4. $L_2 \cup L_3 \:\text{is recursively enumerable.}$
in Theory of Computation by Veteran (99.6k points)
edited by | 3.8k views

1 Answer

+59 votes
Best answer

Recursively enumerable languages are closed under union and intersection. So, lets consider each option

  1. $L_2 - L_1 = L_2 \cap \overline{L_1}$
    Recursive languages are closed under complement, and so $\overline{L_1}$ is recursive and hence recursively enumerable also. So, $L_2 \cap \overline{L_1}$ is recursively enumerable is always TRUE.
  2. $L_1 - L_3 = L_1 \cap \overline{L_3}$
    Recursively enumerable languages are not closed under complement. So, $\overline{L_3}$ may or may not be recursively enumerable and hence we can't say anything if $ L_1 \cap \overline{L_3}$ is recursively enumerable or not. 
  3. Intersection of two recursively enumerable languages is always recursively enumerable(RE closed under intersection).
  4. Union of two recursively enumerable languages is always recursively enumerable(RE closed under union).

For verifying closure properties:

Correct Answer: $B$

by Veteran (418k points)
edited by

Consider L1 as Sigma* . Now option two becomes L3' is RE.But RE but  not REC complement is always Not RE.



@Arjun Sir,In the solution it is mentioned 

L3' may or may not be recursively enumerable

But L3 is RE but not REC and compliment is always NOT RE for this.If L3 is RE then we can say that L3', may or may not be RE,but for RE but Not REC ,compliment is always Not RE.If both are RE then it is recursive.(

@rahul sharma 5

you are right.

But, I have this doubt:

L1- L3 = L1 Intersection L3'

Now, L1= REC and L3' = NOT RE

Then at the best what can we say about L1-L3 ?

@Arjun sir , please help :)

@Vs ,we can not comment.It may or may not be RE.


= L1 ∩ (L3)'

= REC ∩ (REbutNotREC)'


Now consider in L1 we dont have any string .Then we get intersection as phi. Which means regular ,hence RE.

Second case:- Consider L1 as universal language,now final intersection gives NOT RE language.So i dont think we can comment anything.As i have given you two extreme examples that it can be regular and it can be NOT RE



Sir how to solve such kind of  questions in general... Please teach the method or tell some resource from where I can learn.. I cant cram..

Same doubt  , can you please explain me  why we have not used set difference property directly

@Anchit The answer I have given is self explanatory -- there is no more theory involved there. The only thing I used is closure property -- which also need not be mugged up. Most of the closure property comes natural to you if you study TOC from good lectures like that of Shai Simonson. Even now I'll say spending 2 whole days on such videos is worth for GATE.

@Sandeep When a set is "not closed" under an operation we can never say that the result of that operation won't be in that set -- it may or may not. This is the basic rule for using closure property.

@rahul sharma 5,Please can you take example for each of the individual language please?Just to make things bit clear. I meant input for each case. :)
Sir how , intersection of two recursively enumerable languages is recursively enumerable , as we know they are not closed under complementation.
after reading so many comments, I can't come to a conclusion.

It's very confusing .

seeing the options, 1st thing come in mind is to use set difference property, then both A & B are false.

if I use complement with intersection form then option B is false only.

can't understand, what's the problem

@Respected seniors, please help

Related questions

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
49,984 questions
55,138 answers
85,161 users