edited by
286 views
0 votes
0 votes
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 by

1 Answer

2 votes
2 votes

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.

Related questions

1 votes
1 votes
3 answers
2
1 votes
1 votes
1 answer
3
Souvik33 asked Dec 4, 2022
331 views
Consider the following statementS: $\left \{ a^{n}b^{n+k}|n\geq 0,k\geq 1 \right \} \cup \left \{a^{n+k}b^{n}|n\geq 0,k\geq 3 \right \}$ is DCFLThe above statement is:TRU...
0 votes
0 votes
0 answers
4