35 views
Let A and B be disjoint, R.E. languages. Let (A∪B)'   also be recursive enumerable. What can you say about A and B?
(a) Neither A nor B is decidable is possible
(b) At least one among A and B is decidable
(c) Both A and B are decidable
(d) None of above
Solution: Option (c)

how?

edited | 35 views
0
yes decidable

Say, A is all even no.

and B is all odd number

A and B are RE,    (AUB) Complement is RE

(AUB) C = A∩ B------> RE -------> Both Aand BC are RE  // RE languages  are closed under intersection

Since RE languages are not closed under complementation ......Thus  If  A and Aboth are RE implies that A is Recursive (Decidable ), Similarly for B as well.

by Active (1.6k points)

+1 vote