必然是以下语言不可解除

Question

对于a，b不可判定，ab u ba不一定可判定？

我认为答案是否定的。不必要。 我想到了以下示例，但它没有完全反驳：

如果我们服用a和补充，并且没有失去一般性，空词就在a中，而不是一个'中的每一个单词也在aa'u a'a中，但我不能用它来显示每一个单词在a中也在aa'u a'a中。

如果有人可以帮助我如何表明A也可以在AA'U A'A中找到问题。

非常感谢。

Answer 1

采取一些未定的语言 $ a $ ，然后选择 $ b= a'\ bigcup \ {\ epsilon \} $。 $ b $ 也是不可判定的，其余的证据就像你已经完成的那样。