TOC CONCEPTUAL

Question

Which are the correct arguments?
1) if A is a subset of B, and B is decidable, than A is guaranteed to be decidable.
2) If L is Turing-decidable and L' is regular. Then L ∩ L' is regular.
3) The language L = {<D> | D is a DFA and there exists a TM M such that L(M) = L(D)} is Turing-decidable
4) If L₁ reduces to L₂ and L₂ is undecidable, then L₁ is undecidable.

(A) 1, 2, 3
(B) 3, 4
(C) 1, 3
(D) 2, 3

Comments

d???

Answer 1

1. FALSE. Let $B = (0+1)^*$ which is regular. Now any undecidable problem represented in binary is its subset.

2. FALSE. Let $L = \{a^nb^n, n \geq 0 \}$ and $L' = (a+b)^*$. Now, their intersection will be $L$ which is CFL but not regular.

3. TRUE. Every DFA has a corresponding TM which accepts the same language -- because every regular set is also a recursively enumerable set. So, the language here reduces to the set of all valid DFA descriptions which is Turing decidable.

4. FALSE. Any decidable problem can be reduced to an undecidable one and this does not prove anything. If we reduce an unknown problem $X$ to a decidable one, then $X$ becomes decidable. Similarly if we reduce an unknown problem $X$ to a known undecidable problem then $X$ becomes undecidable.

Comments

$L'$ is just another language -- not the complement of $L$.

---

Ok sir....

---

hay option 4 is TRUE

both 3,4 are correct