+1 vote
724 views

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?

1. $S_1$ is correct and $S_2$ is not correct
2. Both $S_1$ and $S_2$ are correct
3. Both $S_1$ and $S_2$ are not correct
4. $S_1$ is not correct and $S_2$ is correct

recategorized | 724 views

+1 vote
• S2 is correct: The set of all Turing machines is countable.
• S1 s also TRUE. $L_2 - L_1 = L_2 \cap L_1'$. Since $L_1$ is recursive $L_1'$ is also recursive and hence r.e. also. And finally r.e. languages are closed under intersection.

So answer is B Both are correct

by Boss (33k points)
selected by
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
by Boss (49.3k points)
+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

by Boss (45.4k points)
0

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

0
@vijay i have written everything what is you doubt i did not understand .

a/c to my knowledge L2-L1 is set difference operation of language L2 and L1 which is RE (given in problem statement.). after they said L1 and L2 individually also RE.