Palindrome

[Alan Kennedy]

[Alan Kennedy]
>> ... There must be some way to have a
>> single fixed regular expression that can be used to test every
>> palindrome.

[Andrew Dalke]
> 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.

Thanks Andrew.

I read up on the topic after posting yesterday (because I had this
vague niggling doubt). After finding that what you stated above is
true, I realised that the vague niggling doubt was actually the memory
of my old compiler-theory lecturer laughing at me :-D

Here's a nice page I found that discusses this and other related
topics.

FINITE STATE AUTOMATA AND REGULAR EXPRESSIONS
http://www.cs.princeton.edu/introcs/71regular/

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

The possibility of the same feature occurred to me. However, I'm still
not sure if this would solve the problem. How would the "pivot point"
be recognised by such an augmented regex engine? i.e. how would it
recognise the point at which it should stop capturing, reverse the
sequence and start matching again?

Perhaps one would need to also implement a feature whereby the length
of the entire string could be made available within expressions, so
that the size of a capture group could be limited to the first half of
the string? I.E. Something along the lines of

^(.{strlen/2}).?\~1$

One of these days I'll find the time to dig out my old course notes
and books :#)

regards,

-- 
alan kennedy
-----------------------------------------------------
check http headers here: http://xhaus.com/headers
email alan:              http://xhaus.com/mailto/alan