The Gateway to Computer Science Excellence
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)

in Theory of Computation by (365 points)
edited by | 35 views
yes decidable

Say, A is all even no.

and B is all odd number

1 Answer

+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.

by Active (1.6k points)

Related questions

0 votes
0 answers
asked Nov 21, 2018 in Theory of Computation by amitqy Active (1.9k points) | 60 views
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,391 answers
105,442 users