Question

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?
1. W can be recursively enumerable and Z is recursive.
2. W can be recursive and Z is recursively enumerable.
3. W is not recursively enumerable and Z is recursive.
4. W is not recursively enumerable and Z is not recursive.

Answer 1

Correct Answer - Option 3 : W is not recursively enumerable and Z is recursive.

Concept:

Language A is reducible to language B (represented as A ≤ B) if there exists a function which will convert A to B.

Rule: If A ≤ B and B is recursive then; A is also recursive.

If A ≤ B and if A is not recursively enumerable, B is also not recursively enumerable.

Explanation;

Here X is a recursive language and X̅ is complement of X. As complement of a recursive language is also recursive, so, X̅ is also recursive.

But complement of recursive enumerable language is not recursive enumerable so, Y̅ is not recursive enumerable.

Now it is given that, Y̅ reduces to W and Z reduces to X̅.

According to the rule, X̅ is recursive. So, Z is also recursive.

But according to the property of recursive enumerable language W is not recursive enumerable language.