Search code examples
automatafinite-automatadfanfaautomata-theory

Is it TRUE that L^R = L, if and only if L is the language of palindromes?

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?

Solution

  • 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.