1. [35 points] For each of the following propositions concerning mapping reducti

Question

1. [35 points] For each of the following propositions concerning mapping reductions, determine whether it's true or false and justify your answer: la. [7 points] For every language L: L is decidable iff L sm 10, 1) 1b. [7 points] For all languages A, B,C: if A Sm B Sm C then A Sm C 1c. [7 points] For all languages A, B: if A Sm B then A sm B. 1d. [7 points] For all languages A, B: if A Sm B and B is regular, then A is regular. le. [7 points] For all languages A, B: if A m B and B is undecidable, then A is undecidable.

Explanation / Answer

Solution:

1)

a)

True

Explanation:

If a machine is possible which is reducible to L then the language L is decidable.

b)

false

we cannot say if m C is reducible to A as well because there is no relation between A and B

c)

false, since CFL and RE are not closed under complementation we cannot say about all the languages

d)

True

Since B is reducible to A

e)

True.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.