I found the following question

Suppose A and B are recursively enumerable languages such that $A∪B=Σ^∗$. Further, suppose $(A∩\overline{B})∪(\overline{A}∩B)$ is decidable. Which of the following is true?
A- It is possible that either A or B is decidable but not both
B- None of them can be decidable
C- Both of them are regular
D- Both of them are decidable

My attempt: It is possible for $A$ & $B$ to be mutually exclusive and yet be exhaustive. Now this can happen even when one of them is not decidable. So $A$.

But answer given id $D$. Are my arguments flawed? If yes, how and where?

The source of the question is reputable test series, but still there are chances of it being wrong.

  • $\begingroup$ What are $A^-$ and $B^-$? $\endgroup$ Jan 17 '19 at 18:52
  • 1
    $\begingroup$ Typo: should be \overline. :) $\endgroup$ Jan 18 '19 at 16:38

It is possible for $A$ & $B$ to be mutually exclusive and yet be exhaustive. Now this can happen even when one of them is not decidable. So option A.

The analysis above is correct except the last conclusion "So option A". We cannot exclude the possibility that $A$ and $B$ are both decidable. In fact, it happens in the current situation because of the extra condition, as shown in the latter part of this answer.

Hints, try using the following facts. If you do not know them, prove them first.

  • For any two languages $X$ and $Y$, if $X$ is exhaustive and $Y$ is decidable, then $X\cap Y$ is exhaustive. (Moreover, $X\setminus Y$ is exhaustive, too. We do not need this fact, though.)
  • For any language $X$, $X$ is decidable if (and only if) both $X$ and $\overline X$ are exhaustive.

Here is how we can find both $A$ and $B$ are decidable.

Since $A$ is exhaustive and $(A\cap \overline B)\cup(\overline A\cap B)$ is decidable, $A\cap ((A\cap \overline B)\cup(\overline A\cap B))=A\cap\overline B$ is exhaustive. Since $A\cup B=\Sigma^*$, $A\cap\overline B=\overline B$. Since $B$ and $\overline B$ are exhaustive, $B$ is decidable.

Symmetrically, $A$ is decidable.

  • $\begingroup$ Yes, but won't the solution be endowed with the fallacy of appealing to consequences? Example $A U B$ can be regular but it doesn't say anything about $A$ & $B$ individually. $\endgroup$
    – Mr. Sigma.
    Jan 17 '19 at 15:13
  • $\begingroup$ It is a fallacy to proceeds like "$A\cup B$ is regular, then both are regular". However, there are other ways to Rome. $\endgroup$
    – John L.
    Jan 17 '19 at 15:23
  • $\begingroup$ "It is possible for A & B to be mutually exclusive and yet be exhaustive." However, if further more, their union is $\Sigma^*$ as in the question, both $A$ and $B$ are decidable by definition then. $\endgroup$
    – John L.
    Jan 17 '19 at 15:29
  • $\begingroup$ Can you use reducibility? $\endgroup$
    – Mr. Sigma.
    Jan 17 '19 at 16:38
  • 1
    $\begingroup$ I like my answer better. :) $\endgroup$
    – John L.
    May 18 '20 at 5:15

Answer by Arjuna

To check whether a string belongs to $A$ run a TM $M$ giving the string as input. $M$ must accept if string is in $A$ and reject if string is not in $A$. Accepting part is trivial as we are told $A$ is recursively enumerable and hence a semi-deciding Turing machine (will always going to $ACCEPT$ state for strings in the language but may not always go to $REJECT$ state for strings not in the language) must exist for $A$. Now, $M$ only needs a way to go to reject state if string is not in $A$. This can be done as follows:

  • If string is not in $A$ it must be in $B$ because $A∪B=Σ∗$
  • But if a string is in $B$ it can also be in $A$.
  • To be sure a string is not in $A$
    • It must be in $B$ -- can be checked using the semi-deciding Turing machine for $B$.
    • It must not be in $A∩B$ -- can be checked using the decider for $(A∩\overline{B})∪(\overline{A}∩B)$. If string is in $A∩B$ the decider TM will definitely go to a REJECT state.

So, our Turing machine $M$ now knows to accept strings in $A$ and reject strings not in $A$. This makes $A$ a recursive language (decidable). Same construction works for $B$ as well. So, both $A$ and $B$ are recursive (decidable).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.