Palindrome

[Andrew Dalke]

Alan Kennedy:
> I'm not too happy with it though. There must be some way to have a
> single fixed regular expression that can be used to test every
> palindrome.

There isn't such a way.  Regular expressions cannot match
strings of the form a**n b**n a**n (pumping lemma).  That's
a palindrome so there are palindromes which cannot be
matched by regular expressions.

There are tricks.  "regular expressions" aren't actually regular
and can be used to match things like a**n b**m a**n (because
of the \1 feature).  However, there still isn't enough to match
a palindrome of arbitrary length. (It would be trivial to add such
a feature -- let \~1 match the reverse of the first match then
  ^(.*).?\~1$
would match all palindromes... slowly.  But no such feature
exists in any regexp engine I know of.)

                    Andrew
                    dalke at dalkescientific.com