1
$\begingroup$

For example I know the union of 2 either decidable or recognizable languages is decidable or recognizable. But say the union of two languages is decidable, does this tell us anything about themselves?

| cite | improve this question | | | | |
$\endgroup$
  • 2
    $\begingroup$ Very little, other than the fact that the union is decidable. The union of a language with its complement is decidable, for example. $\endgroup$ – rici Mar 2 at 23:23
  • 1
    $\begingroup$ @rici Make an answer? $\endgroup$ – Yuval Filmus Mar 3 at 7:45
1
$\begingroup$

No, it doesn't tell us much. Intuitively, union erases information; it's not normally a reversible operation.

So, for example, the union of a language with its complement is clearly decidable and recognizable, regardless of any category in which the language might or might not belong.

| cite | improve this answer | | | | |
$\endgroup$

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.