432 views

3 Answers

Best answer
6 votes
6 votes

$X$ is recursive $\implies \bar X$ is also recursive.

$Y$ is r.e. but not recursive $\implies \bar Y$ is not even r.e.

$\bar X$ reduces to $W \implies $ $W$ is recursive or a super set of it.

$\bar Y$ reduces to $Z \implies $ $Z$ is not even r.e.

Correct Answer: C.

https://gatecse.in/some_reduction_inferences/ 

selected by
0 votes
0 votes
Compliment(REC)=REC                                                 X=REC

Compliment (RE but recursive) = RE                                

Compliment (RE but not recursive) = Not RE                     Y=RE but not REC

i.e W=Compliment(X)=REC

    Z=Compliment(Y)=Not RE

D) is correct
0 votes
0 votes
x complement recursive and y complement not RE hence option D

Related questions