Re: Proposal for matching negated sets (was Re: New Public Review Issue: Proposed Update UTS #18)

From: Hans Aberg (haberg@math.su.se)
Date: Tue Oct 09 2007 - 20:04:59 CDT

  • Next message: Philippe Verdy: "RE: Proposal for matching negated sets (was Re: New Public Review Issue: Proposed Update UTS #18)"

    On 10 Oct 2007, at 01:11, Philippe Verdy wrote:

    > Anyway, you're still not replying to the question: which is the
    > expected
    > ordering for the returned matches?

    If you know what language the grammar produces, then you know the
    language complement. And the DFA construct shows that if the grammar
    is RE (Chomsky hierarchy type 3), there exists an RE grammar that
    produces the complement language.

    > I absolutely don't care if you use a DFA or not.

    So once you have decided what the abstract symbols you use in your RE-
    like algebra should mean grammar-wise (hopefully producing an RE
    grammar), or what DFA they should produce, you can use your favorite
    method to compute an RE grammar that produces the language complement.

    I do not know why this complement operation is important, though.

       Hans Åberg



    This archive was generated by hypermail 2.1.5 : Tue Oct 09 2007 - 20:07:30 CDT