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, $wnotin L$. In addition, for every string $u$ that is not a palindrome either $uin 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), xin [0,1]^*}$. And yet another example $L’ = { x | binary(x) > binary(x^R), xin [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$ $notin$ 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,yin{0,1}^*}$
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/52960
