The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+29 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?

- $L_2 - L_1 \:\text{is recursively enumerable.}$
- $L_1 - L_3 \:\text{is recursively enumerable.}$
- $L_2 \cap L_3 \:\text{is recursively enumerable.}$
- $L_2 \cup L_3 \:\text{is recursively enumerable.}$

+52 votes

Best answer

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

- $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. - $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. - Intersection of two recursively enumerable languages is always recursively enumerable(RE closed under intersection).
- 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

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

+1

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

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

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

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

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.7k
- Digital Logic 2.2k
- Programming & DS 4.1k
- Algorithms 3.6k
- Theory of Computation 4.5k
- Compiler Design 1.7k
- Databases 3.2k
- CO & Architecture 2.8k
- Computer Networks 3.2k
- Non GATE 1.1k
- Others 1.5k
- Admissions 503
- Exam Queries 474
- Tier 1 Placement Questions 22
- Job Queries 61
- Projects 13

39,750 questions

46,765 answers

140,657 comments

58,517 users