The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
78 views

 

in Theory of Computation by Loyal (5.4k points) | 78 views
0
D?
+3
option C

3 Answers

+2 votes
Best answer

$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/ 

by Veteran (416k points)
selected by
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
by Active (1.1k points)
0 votes
x complement recursive and y complement not RE hence option D
by (257 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,823 questions
54,818 answers
189,571 comments
81,050 users