Re: OT: regular expression question

[Frodo Baggins <thehobbit@altern.org>]

Peter Jay Salzman scripsit:
>
>recently, i started wondering if there was a way, using regex only, to
>express a palindrome of arbitrary letter length?
>
>i've used some grey matter, and the answer seems to be no, but there's nice
>symmetry here.  maybe i'm missing something...
>

Well, maybe you're simply forgetting your compilation and formal
languages course:) The answer is NO. Any book on formal language
(cinderella for one;) will explain you way. Simply stated, one can
prove that any regular language, i.e. any set of words that can be
described using a regular expression, has the following property:

There exist an integer n, such that if w is a string belonging to the
language (i.e. matching the regular expression) and longer than n
caracters, then there exists words x, y, and z, such thet:
  
  1 w = xyz
  2 y is not empty
  3 x has less than n caracters
  4 for any integer k, the word w_k = xyy..yz (k times y) is in the
    language (i.e. matches the regex)

Suppose there is a regular expression r describing palindromes,
ie. such that a word match r if and only if it is a palindrome. 

Take the palindrome w=aaa...abb...b where there are n 'a' and n
'b'. By the above property (which, by the way, is known as the "Pumping
Lemma") there exists x, y, z satisfaying 1 to 4 above. By property 2,
x is in the form aa...a and y starts by a. Obviously, xyyz is not a
palindrome. But, for property 4 above, it must match r. So r does not
describe only the palindromes. QED.

-- 
Leo TheHobbit 
IRCnet #leiene
ICQ 56656060

-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GED/CS d? s-:+>-: a C+++ U+++ L++(+++)>++++ P+++>+++++ E+(++) 
W++ N+ K? o? !w O? M V--- PS+++ PE-- Y+ GPG+ t++ 5? X- R+ tv+ 
b++++ D? DI? G e(++++)* h(+) r--(---) y(+)-->+++*
------END GEEK CODE BLOCK------