当且仅当 L 是回文语言时，L^R = L 是否为真？

Question

S1：LR = L，当且仅当L是回文语言。其中LR是将L的所有字符串取反得到的

S1 是真的吗？

Answer 1

反例：

X := { all words w over {a,b}* such that |w| = 2k for some positive integer k and w = reverse(w) }

Reverse(X) = X，但是X不是所有回文的语言，因为"a"是回文，不是X的成员。

另一个反例：

Y := { "abc", "cba" }

Reverse(Y) = Y，但Y中没有一个单词是回文。