The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+29 votes
3k views

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.}$
asked in Theory of Computation by Veteran (101k points)
edited by | 3k views

1 Answer

+52 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:
http://gatecse.in/wiki/Closure_Property_of_Language_Families

answered by Veteran (358k points)
edited by
+1
@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.
0
@arjun Sir, sorry i was talking about option 2
+1

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

0

@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)

0
@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 :)
+2

@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

0

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..

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

@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.

0
@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. :)


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

39,750 questions
46,765 answers
140,657 comments
58,517 users