Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
    
"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 at 13:29
6  
I disagree, what he defined was a class of languages. That does not constitute a well defined definition for a language. – Shreesh Feb 11 at 14:20
up vote 11 down vote accepted

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

share|cite|improve this answer
    
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 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 at 11:53
    
Yes, but will such functions be able to define a total order on $\Sigma^*$? – Marik S. Feb 12 at 11:56
1  
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 at 12:06
1  
And if you take diagonalization language then it becomes non-RE. – Shreesh Feb 12 at 12:10

About generating a few examples:

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)

share|cite|improve this answer
1  
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 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 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 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.)

share|cite|improve this answer
6  
Which leads to an even more explicit description: $L=\{x0y1x^R\ |\ x,y\in\{0,1\}^*\}$. – Klaus Draeger Feb 11 at 23:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.