Re: FYI: Regex paper for UTC

From: Jonathan Coxhead (jonathan@doves.demon.co.uk)
Date: Tue Oct 23 2007 - 02:12:56 CDT

  • Next message: Frank Ellermann: "Re: purl.net/net/cp"

       Philippe Verdy wrote:

    > [...] For me, a regexp is not a string, but [...]

       No, no, no. A "regular expression", by definition, denotes a "regular set".
    This is just basic theoretical comp sci. Some regular sets are finite (and in
    fact any finite set is a regular set). Other regular sets are infinite, which
    means they are not tractable per se on a computer. Which is why we represent
    them as regular expressions.

       For instance, the regular expression /a*/ denotes the (infinite) regular set
    {"", "a", "aa", "aaa", ...}.

       All you need to do to define a regular expression is to define what members
    its regular set has. That's all.

       The question of "matching" is then just a question of set membership. "aa"
    matches the regexp /a*/ because "aa" is in the regular set denoted by /a*/. You
    can ask & answer other questions, like, "What is the longest match?", "What
    elements contain "aa" as a substring?", etc, but let's keep the terminology
    straight. It's not really up for grabs at this point.

    -- 
    ... Jonathan Coxhead
       "People assume that time is a strict progression of cause to effect, but
    actually from a non-linear, non-subjective viewpoint, it's more like a big ball
    of wibbly-wobbly, timey-wimey ... stuff." ---The Doctor
    


    This archive was generated by hypermail 2.1.5 : Tue Oct 23 2007 - 02:16:17 CDT