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 solve this question as shown below.Can you please help me to find the mistake

It is given L2  and L3 are langugages that are recursively enumerable but not recursive.

a) L2 - L1=L2

so recursively enumerable

b)L1 - L3=L1

so  recursive. It means  recursively enumerable also

c)L2∩L1 =empty (I don't know it is recursively enumerable or not)

d)L2 ∪L1 is  recursively enumerable

---

The diagram you have drawn is for the set of languages which constitute recursive/recursively enumerable languages, which are called language families. Now L1, L2 and L3 are individual languages. So, the subset relation need not hold for them.

For example,
{{1},{2}}  ⊂ {{1},{2},{3}}, but {1} ⊄ {2}

So, your second figure is not correct.

---

Even though L1,L2,L3 individual languages L1 present some where in that white portion and L2,L3 somewhere in that black portion.Isn't it?

---

yes. That is correct.

---

But we can't use that diagram to decide L1-L2 etc., because this depends on what is inside L1, L2 etc, which is not shown in that diagram..

---

thank you :)

---

L2 - L1 is recursive and hence R.E. Right ??

---

No. How can we say it is recursive?

---

L1' is recursive and L2 is R.E. So L2 intersection L1' is recursive. Is it not true ??

---

Ok.. we can apply L2 intersection L1' only if L1,L2 represent family of language.. Right ??

---

No. We can apply intersection for any sets. Both an individual language (set of strings) and family of languages (set of languages) are sets and hence we can apply intersection.

But a recursive language intersection r.e. language can only be r.e. as r.e. is closed under intersection. It may or may not be recursive.

---

ok.. and what about the pic (Chomsky hierarchy) posted above.. we should use it only when we have family of language with us.. Right ??

---

The pic is for family of languages. But it can be used for individual languages also if we use properly.

---

I also thought the same way as Anu has done. But i am unable to understand that why this method is wrong?

---

Complement of $L1 - L3$ will be Recursively Enumerable for sure right?

---

Yes

---

arjun sir i have a very very confusing doubt. please clear it.

L2 is RE and L1 is recursive and hence RE language. Now both L1 and L2 are RE languages and we know RE languages are not closed under set difference. So it concludes L2-L1 is also not RE.

In your solution you converted set difference to intersection and come to the correct solution.

How is this justified?? please answer it.

---

Most people have this confusion. This is very very important for GATE or any such exams - not just for TOC.

"not closed"

"not valid or invalid"

"not decidable or undecidable"

These are complements of closed, valid and decidable respectively. Okay, now all these operate on sets and each of them is a property on the set- i.e., for elements of the set. Even if one element violate propery, we say the property does not hold for the set. Now lets see for closed.

A set is closed under an operation if when we operate an element(s) on that operator we get another element from the set.

Now, for set of r.e. languages, even if there are two languages $L_1$ and $L_2$ such that $L_1 - L_2$ as non r.e. we can say that set of r.e. languages are not closed under set difference. But not-closed never says that for any two r.e. languages $L_1$ and $L_2$, $L_1 - L_2$ WILL ALWAYS BE non.re. Rather it MAY OR MAY NOT be r.e.

---

Arjun sir that i understand that not closed meand may or may not be. But if for any instance its not closed we will in general say not closed. However even with this logic i am not able to reach to the correct solution. Okay if two RE languages are taken and their set difference is considered what will we answer- may not be closed or n0t closed.???

---

If Indian President is in front of you and you are asked if he is a male or female what will you answer? Or how will you answer?

---

Sir please clear my doubt. I just wanna ask that in case of not closed- shall we answer may or may not be closed or not closed since not closed doesnt mean that every instance will be not closed. please

---

You are abusing the meaning of "closed".

in case of not closed- shall we answer may or may not be closed

You yourself said that it is not closed. There is not a thing called "may or may not be closed" unless we are taking about a set and an operator whose closure property we are not sure of.

What you are not getting is "closed is for a set and not for its elements".

---

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.