The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
30 views
9. Let L ≤ ML’ denote the language L is mapping reducible (many to one reducible) to language L’. Which one of the following is True?
(a) If L ≤ pL’ and L’ is semidecidable then L is semidecidable.
(b) If L ≤ pL’ and L is RE then L’ is RE.
(c) If L ≤ pL’ and L is decidable then L’ decidable.
(d) If L ≤ pL’ and L is recursive.
Solution: Option (a)
PLEASE Explain
closed as a duplicate of: GATE2014-2-16
asked in Theory of Computation by Active (1.3k points)
closed by | 30 views
+1

https://gateoverflow.in/1972/gate2014-2-16 u can find the same question here. moreover for better understanding in more simpler way you can take it as:

L(TRUE)<------L'(TRUE)

L(FALSE)--------> L'(FALSE)

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,072 questions
49,594 answers
162,957 comments
65,788 users