Question

4. Given two languages A and B, show that if An B and AUB are decidable, then A is decidable.

Answer 1

Let M and N be the decidable Turing machine for first and second decidable language given above respectively .

Now the membership for A can be decided for all 4 possible cases as follows :-

1. If input x is in A and B as well.

In this case, M will accept x and hence accept x if x is accepted by M.

2. If x is in A but not in B.

In this case M will not accept x(as it is not in B) and N will not accept x(as it is not in complement of A and not in B) and hence accept x if neither M nor N accept it.

3. If x is not in A but in B.

In this case M will not accept x but N will accept it(since x is in B) and hence reject x if this happens.

4. If x is not in A and not in B as well

In this case, M will reject x but N will accept it(since x is in complement of A) and hence reject x if this happens .

Since all the 4 cases, the behavior of Turing machine M and N are different when x is in A than when x is not in A and hence we will be able to decide A and hence A is decidable.

Please comment for any clarification .