Question

Assume statements S1 and S2 defined as: S1: L2-L1 is recursive enumerable where L1 and L2 are recursive and recursive enumerable respectively. S2: The set of all Turing machines is countable. Which of the following is true?

(a) S1 is correct and S2 is not correct

(b) Both S1 and S2 are correct

(c) Both S1 and S2 are not correct

(d) S1 is not correct and S2 is correct

I have been asked this question in an online quiz.

My doubt is from Context Free Grammar in section Contextfree Grammar and Syntax Analysis of Compiler

Answer 1

Right choice is (b) Both S1 and S2 are correct

For explanation: The assumptions of statement S1 and S2 are correct.