Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things

Comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
(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.)


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


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

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, 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, 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.
  • Log In?

    What's my password?
    Create A New User
    [marto]: The_Venture_Bros.. highly recommended

    How do I use this? | Other CB clients
    Other Users?
    Others making s'mores by the fire in the courtyard of the Monastery: (5)
    As of 2018-02-21 11:27 GMT
    Find Nodes?
      Voting Booth?
      When it is dark outside I am happiest to see ...

      Results (279 votes). Check out past polls.