GATE2010-17

Question

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?

• A. $L_2 - L_1 \:\text{is recursively enumerable.}$
• B. $L_1 - L_3 \:\text{is recursively enumerable.}$
• C. $L_2 \cap L_3 \:\text{is recursively enumerable.}$
• D. $L_2 \cup L_3 \:\text{is recursively enumerable.}$

Answer 1

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

• A. $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.
• B. $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. 
• C. Intersection of two recursively enumerable languages is always recursively enumerable(RE closed under intersection).
• D. Union of two recursively enumerable languages is always recursively enumerable(RE closed under union).

For verifying closure properties:
http://gatecse.in/wiki/Closure_Property_of_Language_Families

Correct Answer: $B$

Comments

i was talking in this context-

But not-closed never says that for any two r.e. languages L1 and L2 , L1−L2 WILL ALWAYS BE non.re. Rather it MAY OR MAY NOTbe r.e.

Closure property is a helping technique to know the class of the resulting language when we do an operation on two languages of the same class. That is, suppose L1L1 and L2L2belong to CFL and if CFL is closed under operation ∪∪, then L1∪L2L1∪L2 will be a CFL. But if CFL is not closed under ∩∩, that doesn’t mean L1∩L2L1∩L2 won’t be a CFL. For a class to be closed under an operation, it should hold true for all languages in that class. So, if a class is not closed under an operation, we cannot say anything about the class of the resulting language of the operation – it may or may not belong to the class of the operand languages. In short, closure property is applicable, only when a language is closed under an operation.

---

What is confusing there?

---

@Arjun sir, in option 3  L1-L3 is a subset of L1 so its strings can be accepted by the same TM as that of L1 .So it must be recursively enumerable definitely. please correct me if i am wrong.

---

@arjun Sir, sorry i was talking about option 2

---

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

See https://gateoverflow.in/1810/gate2014-1-35

---

@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.(https://gateoverflow.in/1810/gate2014-1-35)

---

@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 

= L1 ∩ (L3)'

= REC ∩ (REbutNotREC)'

=REC ∩ NOT RE

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

---

@ Arjun

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

---

complement of a RE but not REC language can never be RE.

complemet of a RE language can be RE .

 

if complement of a language is RE but not REC then that language must be NOT RE.

 

 

explaination -

A language L is RE but not REC means that the language is not decidable.  which means there exist a turing machine which halts for the members of language but may or may not halt for non members. ( there  must exist some non members in L for which TM doesn't halt otherwise it would become Halting TM which would mean L is recursive)

you say that complement of this language (say L' ) is RE .  it means that a turing machine exist that will halt for all members of L' .

But all members of L' are nothing but all non members of L and if a turing machine is there that halt for all non members of L whose members are already accepted by a TM. it simply means that language wasn't "RE but not REC" in the first place , instead the language is REC and and hence its complement also REC.

---

L2 = RE but not REC

L1 = REC = L1 complement

Now, as per the graph, L2 ∩ L1(comp) = Φ as the Chomsky hierarchy. The same goes for option B.

Please confirm if I am wrong.

Option A and B both are wrong.

---

@Arjun sir, in this question (https://gateoverflow.in/1379/gate2005-56) you said that , if the language is Rec.enu. and not Recursive than the complement of that language can be said as NOT Rec.enu. , So why in this question in option (B) you said the complement of language “may or may not be” Rec.enu., I mean it should be ofcourse NOT Rec.enu according to your comment on that referred answer.

---

L1-L3 means we get a set containg strings in L1 and  not in L3 . So it is a subset of L1 and L1 is aleady recursive then how can se say that L1-L3 may not be recursive enumerable.

---

L1 is recursive languange

L2 is not recursive enumerable language

l

what can we say about L1 intersection L2

is result is recursive or not recursive enumerable

---

I have a doubt…...….

(RL) U  (CFL) = CFL because every RL is CFL and CFL  is closed under  union. 

Now in  (RL) ⋂ (CFL) = CFL 

my doubt is every RL is CFL and CFL  is not closed under intersection so it can be CFL or non-CFL(which is recursive). Hence in (RL) ⋂ (CFL)  we can also get recursive language.

 

Answer 2

I hope this makes it simpler!

 

Comments

I don’t think this is the correct logic. In your case L1-L3 is always a subset of L1(which is REC), therefore REC ENUM.

L1 can be universal language, in that case L1-L3 will be L3’ which may or nay not be REC ENUM. you can refer to above discussion