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:** Since X is recursive and recursive language is closed under complement. So X’ is also recursive.

Since Z ≤ X’ is recursive. (Rule : if Z is reducible to X’ , and X’ is recursive, then Z is recursive.)

Option (B) and (D) is eliminated.

And Y is recursive enumerable but not recursive, so Y’ cannot be recursively enumerable.

Since Y’ reduces to W.

And we know complement of recursive enumerable is not recursive enumerable and therefore, W is not recursively enumerable. So **Correct option is (C)**.

Here Y’ is complement of Y

and X’ is complement of X.