Gate CS-2016-1 Question Paper With Solutions

Q.54 Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that Y’ reduces to W, and Z reduces to X’ (reduction means the standard many-one reduction). Which one of the following statements is TRUE

(A) W can be recursively enumerable and Z is recursive.

(B) W an be recursive and Z is recursively enumerable.

(C) W is not recursively enumerable and Z is recursive.

(D) W is not recursively enumerable and Z is not recursive

Answer: (C)

Explanation:

Gate CS-2016-1 Question Paper With Solutions

Learn More:   Gate CS-2017-2 Question Paper With Solutions

LEAVE A REPLY

Please enter your comment!
Please enter your name here