Let A ≤m B denotes that language A is mapping reducible (also known as many-to-one reducible) to language B. Which one of the following is FALSE?

If A ≤m B and B is recursive then A is recursive

If A ≤m B and A is undecidable then B is undecidable.

If A ≤m B and B is recursively enumerable then A is recursively enumerable

If A ≤m B and B is not recursively enumerable then A is not recursively enumerable

Let ∑ be a finite non-empty alphabet and let 2∑* be the power set of ∑*. Which one of the following is TRUE?

Both ) 2∑* and ∑* are uncountable

Both 2∑* and ∑* are countable

2∑* is countable and ∑* is uncountable

2∑* is uncountable and ∑* is countable

Both ) 2∑* and ∑* are uncountable

Explore topic-wise MCQs in Computer Science.

This section includes 2 Mcqs, each offering curated multiple-choice questions to sharpen your Computer Science knowledge and support exam preparation. Choose a topic below to get started.

1.	Let A ≤m B denotes that language A is mapping reducible (also known as many-to-one reducible) to language B. Which one of the following is FALSE?
A.	If A ≤m B and B is recursive then A is recursive
B.	If A ≤m B and A is undecidable then B is undecidable.
C.	If A ≤m B and B is recursively enumerable then A is recursively enumerable
D.	If A ≤m B and B is not recursively enumerable then A is not recursively enumerable
Answer» E.

Discussion

2.	Let ∑ be a finite non-empty alphabet and let 2∑* be the power set of ∑*. Which one of the following is TRUE?
A.	Both 2∑* and ∑* are countable
B.	2∑* is countable and ∑* is uncountable
C.	2∑* is uncountable and ∑* is countable
D.	Both ) 2∑* and ∑* are uncountable
Answer» D. Both ) 2∑* and ∑* are uncountable

Discussion