S1: LR = L, if and only if L is the language of palindromes. where LR is obtained by reversing all the strings of L.
Is S1 TRUE?
Counterexample:
X := { all words w over {a,b}* such that |w| = 2k for some positive integer k and w = reverse(w) }
Reverse(X) = X
, but X
is not the language of all palindromes, as "a"
is palindrome and is not a member of X
.
Another counterexample:
Y := { "abc", "cba" }
Reverse(Y) = Y
, but no word in Y
is a palindrome.