Syntactic Confectionery Delight  
PerlMonks 
Re: Why machinegenerated solutions will never cease to amaze meby tmoertel (Chaplain) 
on Nov 10, 2004 at 18:27 UTC ( #406746=note: print w/ replies, xml )  Need Help?? 
(Updated 20041111: Pointed out allornone matching constraint that applies here. If you read this post, please also read the followon thread started by hv for more regexpprobing fun.) (Updated: Added quotation for context; added conclusion.) Regarding: And try as I might, I can't find a string that behaves differently between the two. I've tried all the possibilities I can think of, like sadad salalad saladad slad sal, but they behave identically. I still have a nagging doubt that there may be a difference; if anyone can point it out I be most appreciative.There's no difference because we can prove that the regular expressions are equivalent for any atomic regexes x and y (when constrained to allornone matching, which is the case in the original poster's question): (xy)? === (x?y) === (xy?)The proof goes as follows. (Note: I use (x) instead of (?:x) to denote grouping.)
(The proof for the (x?y) case follows immediately from regex union being commutative.) To use your example, let x = (?:al) and y = (?:pre) and the same proof applies. That's why you can't find a string that matches s(?:alpre)?ad differently than s(?:(?:al)?pre)ad – there isn't one. Sometimes it's easier to go after the proof than the counterexample. : ) Cheers, Tom Moertel : Blog / Talks / CPAN / LectroTest / PXSL / Coffee / Movie Rating Decoder
In Section
Meditations

