@Sir...what is meaning of - " L2-L1 is RE, where L2 and L1 are RE.

Acc. to me - It is given that ..L1 and L2 are RE, and now it is saying that L2-L1 will be RE.

Please clear my doubt ..

The Gateway to Computer Science Excellence

+1 vote

Assume statements $S_1$ and $S_2$ defined as:

$S_1$: $L_2 – L_1$ is recursive enumerable where $L_1$ and $L_2$ are recursive and recursive enumerable respectively.

$S_2$: The set of all Turing machines is countable.

Which of the following is true?

- $S_1$ is correct and $S_2$ is not correct
- Both $S_1$ and $S_2$ are correct
- Both $S_1$ and $S_2$ are not correct
- $S_1$ is not correct and $S_2$ is correct

+1 vote

Best answer

+3 votes

S1 is : L2-L1 is recursive enumerable where L1 and L2 are recursive and recursive enumerable respectively.

and ans is B both are correct

set of turing machines is countable but the set of all languages are uncountable

and ans is B both are correct

set of turing machines is countable but the set of all languages are uncountable

+1 vote

Answer : Both S1 and S2 are correct

Recursive enumerable Languages are not closed under set difference operation .But good thing about Statement S1 is as they mentioned that "L2–L1 is recursive enumerable where L1 and L2 are recursive enumerable respectively."

if L1 and L2 are Recursive enumerable then it is not sufficient to say that L2 - L1 will be Recursive enumerable because it violates the closure property.but they have already mentioned that L2 - L1 is Recursive enumerable and along with that L1 and L2 are also recursive enumerable this statements would eliminate the possibilities to make this statement S1 wrong.

Reference : Recursively enumerable language

Statement S2 is also true which is "The set of all Turing machines is countable.".

Reference : Countable TM

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,385 answers

198,560 comments

105,387 users