# Finding examples of languages that are “anti-palindromic”

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

• "I could not find any languages that have this property." -- you have just defined one by giving the property, assuming that there is any language that fulfills the condition. – Raphael Feb 11 '16 at 13:29
• I disagree, what he defined was a class of languages. That does not constitute a well defined definition for a language. – Shreesh Feb 11 '16 at 14:20

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\}^*\}$

• I see, so it is true that every anti-palindrome language is non-regular. But can it be said that it must be in $R$? because even expanding this idea every order/function we will use can be computed with a TM in $R$..right? – Marik S. Feb 12 '16 at 11:37
• @Marik There are well-defined but uncomputable functions. For example mapping from numbers representing M,w in Halting problem to [0,1]. – Shreesh Feb 12 '16 at 11:53
• Yes, but will such functions be able to define a total order on $\Sigma^*$? – Marik S. Feb 12 '16 at 11:56
• Yes. For example $L = \{x | x \neq x^R, binary(x) < binary(x^R)$ if both $x$ and $x^R \not\in$ or $\in$ Halt, otherwise $x$ or $x^R$ whichever is in Halt$\}$. Halt is all $(M,w )$such that $M$ halts on $w$. – Shreesh Feb 12 '16 at 12:06
• And if you take diagonalization language then it becomes non-RE. – Shreesh Feb 12 '16 at 12:10

Building on the answer of @shreesh, we can prove that every anti-palindrome language must be of the form $$L = \{ x \ |\ x < x^R \}\qquad (*)$$ for some strict total ordering $<$.

Indeed, given any anti-palindrome $L$, we can define an associated $<$ as follows. We start by taking any enumeration $x_0,x_1,\ldots$ of $\{0,1\}^*$, where each word occurs exactly once. Then, we alter the enumeration: for each pair of non-palindromes $x,x^R$, we swap their position so to make the one that belongs to $L$ to appear before the other. The new enumeration induces a total ordering $<$ satisfying $(*)$.

That every $L$ defined as $(*)$ is non-palindrome is trivial, so $(*)$ is a complete characterization of non-palindrome languages.

Addressing the original question, we now know that we can obtain several examples of anti-palindrome languages $L$ by crafting orderings $<$. We also know that by doing that we are not restricting ourselves to a subclass of languages, losing generality.

About the question "can these languages be regular?":

To prove that any anti-palindrome $L$ is non regular, assume by contradiction it is regular.

1. Since regularity is preserved by reversal, $L^R$ is also regular.
2. Since regularity is preserved by union, $L \cup L^R$, which is the set of all the non-palindromes, is also regular.
3. Since regularity is preserved by complement, the set of all palindromes is regular.

From the last statement, we can derive a contradiction by pumping. (See e.g. here for a solution)

• Or more simply, you can observe that in order for a DFA to accept the language of palindromes, it needs to consider the first half of the string while parsing the second half -- but a DFA has a finite number of states and cannot store an arbitrarily long string. It's the same reasoning that shows the language of balanced parentheses is non-regular (paren-depth can be arbitrarily large). – Kevin Feb 12 '16 at 4:41
• I see, but if any $L$ that has this property if from the form $L=\{ x | x<x^R \}$ does it indicate that every language is also Context Free? Or if not CFL, then must it be in $R$? since every order $<$ can be calculated in $R$ with a TM. – Marik S. Feb 12 '16 at 11:34
• @MarikS. The grammar of rici below proves that $L$ can be context-free. I'm pretty sure that some $L$ is non-recursive, since there are uncountably many such languages -- in my proof above we can make countably infinite choices about which to put first between $x$ and $x^R$, and each combination gives a distinct $L$. So the cardinality of such languages is the same of $\{0,1\}^{\mathbb{N}}$, which is uncountable. – chi Feb 12 '16 at 16:22

For what it's worth, here is a simple context-free grammar for one anti-palindromic language:

\begin{align} S &\to 0 S 0 \mid 1 S 1 \mid 0 X 1 \\ X &\to \epsilon \mid X 0 \mid X 1 \end{align}

(In fact, this is the anti-palindromic language proposed by @shreesh, using lexicographic comparison for the less-than operator.)

• Which leads to an even more explicit description: $L=\{x0y1x^R\ |\ x,y\in\{0,1\}^*\}$. – Klaus Draeger Feb 11 '16 at 23:35