retagged by
2,960 views
6 votes
6 votes
Let $A$ and $B$ be disjoint, R.E. languages. Let $\bar A \cup \bar 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
retagged by

4 Answers

Best answer
5 votes
5 votes

The question has some redundant data. 

It is given $A$ and $B$ are disjoint. So, $A \cap B = \emptyset \implies A' \cup B' = \Sigma^*$ which is regular (and hence r.e. also). So, "Let  $A' \cup B'$ also be recursive enumerable" is not necessary in question. 

Now, I say option A is true which implies options B and C are false as option A says both $A$ and $B$ can be non r.e. Example for such an $A$ and $B$ is given below.. 

$A = L_1 = \{\langle M,w,0 \rangle \mid M \text{ halts on } w\}$

$B = L_2 = \{\langle M,w,1 \rangle \mid M \text{ halts on } w\}$

Here $L_1$ and $L_2$  (variants of halting problem) are r.e. and neither is recursive. The last bit is added to ensure $L_1 \cap L_2 = \emptyset$. 

edited by
1 votes
1 votes

Given  A and B , disjoint  and recursively enumerable and   A' U B' is RE -- (1)

Given A and B are disjoint. i.e A ∩ B =

(A ∩ B)' = ' =Σ *

A' U B' = Σ *  --- (2)

Both (1) and (2) says there exist a TM which accepts A' U B'   

 

Proof By contradiction:

Assume A and B are RE but not Recursive . [ i.e undecidable/semi-decidable ] 

 

Then A ∩ B also RE but not Recursive [ because RE but not Recursive closed under intersection]

=> (A ∩ B)' is Non RE , [  because RE but not Recursive  Not closed under complement ]  

=> There is no TM which accepts (A ∩ B)' i.e A' U B' 

which contradicts with inference drawn from (1) and (2)

 

=> A and B are Recursive . so They are decidable. 


edited by
0 votes
0 votes

A ∩ B = 

Let L= ∩ B

L' =(A ∩ B)' =A' ⋃ B'

So, L is R.E.

      L' is R.E.

So, we can say L is decidable ( because here 'yes' and 'no' both ans possible for L )

Now for A and B

if A and B both are R.E. then  ∩ B= R.E. ,i.e. fine

but (A' ∩ B')  here the problem comes

if A is R.E. , A' maynot be R.E. , as R.E. not closed under complement

Similarly for B too

So, anyone of A and B is R.E. ,  then L' maynot be R.E.

So, both of A,B should be recursive

Then we can say A and B both are decidable

So, (C) is the answer

edited by
–1 votes
–1 votes

A' ' ' ∪ B' ' ' = A' ∪ B' = (A ∩ B)'

Now if we take both A and B as decidable(i.e. recursive language), then resultant language will also be recursive language as recursive languages are closed under intersection and complementation.

Also all recursive languages are recursively enumerable too. Hence C is the answer. @Arjun Have a look

Related questions