For A,B that are not decidable, does AB U BA not necessarily decidable?

I think that the answer is NO. Not necessarily. I thought about the following example, but it does not refute exactly:

If we take A and A complement, and without losing generality the empty word is in A, than every word in A' is also in AA' U A'A, but I can't use it to show that every word in A is also in AA' U A'A.

If someone can help me how can I show that also A is in AA' U A'A the problem will be solved.

thank you very much.


Take some undecidable language $A$ and choose $B=A'\bigcup \{\epsilon\}$. $B$ is also undecidable, and the rest of the proof is just as what you have already done.


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.