Is { w | w <> w^R } over the alphabet {0,1} a context-free language?

13
votes

I'd really love your help with this deciding whether the language of all words over the alphabet {0,1} that can't be read from both sides the same way, { w | w <> wR }, is a context-free language (that is, it can be transformed into specific grammar rules).

I tried to prove that it is not a context-free language by the pumping lemma, but I didn't find a string which will lead me to contradiction.

Any suggestions?

2
context-free-grammarcomputation-theory
Now that a bounty is on it, it may not apply, but I figure you'd get much better attention for this question on the stackexchange for computer science, theoretical computer science or math. – Corbin
Sans minor fixups, this is a really good question. Corbin is correct about the potential to migrate this over to one of the other StackExchanges. In the meantime, there's lots and lots of information on the decidability of this problem on CSTheory.SE. – MrGomez
I believe <> is "not equal" and "^R" is a "string reversal" operator. – Kaganar
@Corbin: The CS Theory SE has listed in their FAQ that only research-level (i.e. graduate student/professor) questions should go there (similar with MathOverflow). But I agree that Math.SE or CS.SE would be a better place for this. – goric
@goric Ah, I knew the theoretical CS SE had a very high standard, but didn't know that they explicitly stated that. Good to know! (Also, math.stackexchange is any level of math, and mathoverflow research level) – Corbin

2 Answers

12
votes

If I'm reading your question correctly, you're looking to see if the set of non-palindromes is a context free language.

It is a context free language:

S --> 0S0 | 1S1 | R
R --> 0V1 | 1V0
V --> 0V0 | 1V1 | R | 1 | 0 | ε

Starting at S, the notion is to build the string from the outside in. S allows you to place as many matching ones or zeroes as you want (possibly none) until you reach a case of R in which there is a non-match. From there on you can place either matches or non-matches (because at this point we're already guaranteed to not be a palindrome.) This is sufficient to describe all non-palindromes -- from outside to in, they start with zero or more matching pairs, then one mismatching pair, and then zero or more pairs (matching or not). Finally, there may or may not be a character in the middle.

P.S. If you don't already have it, Sipser's book on Theory of Computation is undoubtedly excellent. In fact, it's the only college book I still read from time to time.

2
votes

This question is admittedly over my head as a computer scientist. But, as a mathematician, I have something to contribute here.

If w is itself a context-free language, a closure exists to solve the reversal of w:

Context-free languages are closed under the following operations. That is, if L and P are context-free languages, the following languages are context-free as well:

...

  • the reversal of L

This seems to be all that's being asked here. These references offer additional background information on how the initial and subsequent closed forms are derived.

(Additional, potentially helpful reference from set theory)