recategorized by
4,100 views
3 votes
3 votes

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 by

3 Answers

Best answer
1 votes
1 votes
  • 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

selected by
3 votes
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
1 votes
1 votes

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

Answer:

Related questions

1 votes
1 votes
1 answer
1
go_editor asked Jul 22, 2016
2,730 views
The language $L=\{a^n b^n a^m b^m \mid n \geq 0, m \geq 0 \}$ isContext free but not linearContext free and linearNot context free and not linearNot context free but line...
1 votes
1 votes
0 answers
3
go_editor asked Jul 22, 2016
972 views
Non-deterministic pushdown automaton that accepts the language generated by the grammar: $S \rightarrow aSS \mid ab$ is$\delta (q_0, \lambda , z)= \{ (q_1, z) \}; \delta...