Finding examples of languages that are "anti-palindromic"

Problem Detail: 

Let $\Sigma = \{ 0, 1 \}$. A language $L \subseteq \Sigma^* $ is said to have the "anti-palindrome" property if for every string $w$ that is a palindrome, $w\notin L$. In addition, for every string $u$ that is not a palindrome either $u\in L$ or $\mathrm{Reverse}(u) \in L$, but not both(!) (exclusive or).

I understand the anti-palindrome property, but I could not find any languages that have this property. The closest one I could find is $\Sigma^* \setminus L$, but it does not have the exclusive or part... that is, for example, both $01$ and $10$ are in $L$.

Could anyone give me an example of a language that has this propery? Or possibly even more than a single example, because I fail to see what kind of limitations this puts on a language. (Must it be non-regular? Context Free? Or not even in $R$? and etc.)

Asked By : Marik S.

Answered By : Shreesh

One example will be $L = \{ x\ \ |\ \ binary(x) < binary(x^R), x\in [0,1]^*\}$.

And yet another example $L' = \{ x\ \ |\ \ binary(x) > binary(x^R), x\in [0,1]^*\}$.

The idea is, if $x \neq x^R$ you make a rule to choose only one of them. You need to choose the rule such that palindromes should be rejected ($f(x) < f(x^R)$, for palindromes you must have $f(x)= f(x^R)$).You can also change the alphabet, I took binary alphabet just to get a quick answer.

$L$ and $L'$ above are not regular. And every anti-palindromic language will be non-regular and can be as bad as a non-RE language. Examble of an undecidable language: $L=\{x\ \ |\ \ $such that $ binary(x)<binary(x^R)$ if both $x$ and $x^R$ $\not\in$ Halt or both $x$ and $x^R$ $\in$ Halt, otherwise if $x \in$ Halt$\}$

Klaus Draeger explained in the comment below that anti-palindromic language given at the beginning of the answer is context-free: $L=\{x0y1x^R\ |\ x,y\in\{0,1\}^*\}$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/52960