(Updated 2004-11-11: Pointed out all-or-none matching constraint that applies here. If you read this post, please also read the follow-on thread started by hv for more regexp-probing 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 all-or-none matching, which is the case in the original poster's question):
(x|y)? === (x?|y) === (x|y?)
The proof goes as follows. (Note: I use (x) instead of (?:x) to denote grouping.)

  1. We start with (x|y)?
  2. We can rewrite as (x|y)|E because, by definition, r? is equivalent to r|E where E matches the empty string.
  3. We can rewrite as x|(y|E) because regex union | is associative.
  4. And rewrite as x|(y?), again by definition of ?
  5. And as x|(y?|0) because the regex that never matches anything – 0 – is the identity for union.
  6. And as (x|y?)|0 by associativity.
  7. And finally as (x|y?), again, because 0 is the identity for union.

(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(?:al|pre)?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

Tom Moertel : Blog / Talks / CPAN / LectroTest / PXSL / Coffee / Movie Rating Decoder

In reply to Re: Why machine-generated solutions will never cease to amaze me by tmoertel
in thread Why machine-generated solutions will never cease to amaze me by grinder

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.