2,208 views
3 votes
3 votes
If L1 and L2 are Turing-Recognizable then L1 ∪ L2 will be
(a) Decidable
(b) Turing-recognizable but may not be decidable
(c) May not be Turing recognizable
(d) None of above

1 Answer

6 votes
6 votes

Answer -(b) Turing-recognizable but may not be decidable

Turing-recognizable languages (recursive enumerable languages) are closed under the UNION operation. so, (L1 U L2) will be Turing-recognizable language. 

but, we think for (L1 U L2) will decidable : then according to definition of decidable(recursive)languages holding both the following conditions---

  • (L1 U L2 ) will be Turing-recognizable. 
  • (L1 U L2)'   will be Turing-recognizable .

 here, (L1 U L2 ) will be Turing-recognizable, but (L1 U L2)'   will not Turing-recognizable.     because,

(L1 U L2)' = L1' ⋂ L2'

L1' and L2' will not be Turing recognizable because Turing-recognizable languages (recursive enumerable languages)  are not closed under the COMPLEMENT operation. so, (L1 U L2)' will not be Turing-recognizable .

so, L1 U L2 may not be decidable .

Related questions