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?

W is not recursively enumerable and Z is not recursive.

W can be recursively enumerable and Z is recursive.

W can be recursive and Z is recursively enumerable.

W is not recursively enumerable and Z is recursive.

Let X be a recursive language and Y be a recursively enumerable but no

1.	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 can 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» D. W is not recursively enumerable and Z is not recursive.

Discussion

No Comment Found

Related MCQs

Consider the following sets:S1. Set of all recursively enumerable languages over the alphabet {0,1}S2. Set of all syntactically valid C programsS3. Set of all languages over the alphabet {0,1}S4. Set of all non-regular languages over the alphabet {0,1}Which of the above sets are uncountable?
If L ϵ NP is a language such that L' ≤p L for some L' ϵ NPC, then:
Let A and B be finite alphabets and let # be a symbol outside both A and B. Let f be a total function from A* to B*. We say f is computable if there exists a Turing machine M which given an input x in A*. always halts with f(x) on its tape. Let Lf denote the language {x # f(x) |x ∈ A*}. Which of the following statements is true:
If \( L\) and \(\bar L\) are recursively enumerable, then L is
Consider the following languages.L1 = { | M takes at least 2016 steps on some input},L2 = { | M takes at least 2016 steps on all inputs} andL3 = { | M accepts ϵ},Where for each Turing machine M, denotes a specific encoding of M. Which one of the following is TRUE?
Let L1 be regular language, L2 be a deterministic context free language and L3 a recursively enumerable language, but not recursive. Which one of the following statements is false?
Consider the following statements.I. The complement of every Turing decidable language is Turing decidableII. There exists some language which is in NP but is not Turing decidableIII. If L is a language in NP, L is Turing decidableWhich of the above statements is/are true?
Language L1 is polynomial time reducible to language L2. Language L3 is polynomial time reducible to L2, which in turn is polynomial time reducible to language L4. Which of the following is/are true?I. if L4 ∈ P, then L2 ∈ PII. if L1 ∈ P or L3 ∈ P, then L2 ∈ PIII. L1 ∈ P, if and only if L3 ∈ PIV. if L4 ∈ P, then L1 ∈ P and L3 ∈ P
Consider the following two statements about regular languages:S1: Every infinite regular language contains an undecidable language as a subset.S2: Every finite language is regular.Which one of the following choices is correct?
Let G1 and G2 be arbitrary context free languages and R an arbitrary regular language.Consider the following problems:(A) Is L(G1) = L(G2)?(B) Is L(G2) ≤ L(G1)?(C) Is L(G1) = R?Which of the problems are undecidable ?Choose the correct answer from the options given below:

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?

Discussion

No Comment Found

Related MCQs

Reply to Comment