jakarta-oro-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Michael Borodiansky" <mboro...@home.com>
Subject Re: Question:
Date Fri, 30 Mar 2001 14:37:11 GMT
Thanks a lot!

I know that proving that one DFA is a full subset of another DFA is a
polinomial problem, therefore solveable.
Perl5 regular expressions: What you say is that Perl5 expressions are not
regular language?
Why?

The reason I directed this question here, is because I thought it would be a
nice feature in ORO.
And also, there might have been a provision for that in there.

But please, could you tell me whether you think Perl5 expressions are not
regular language?

Please and thanks,

    Michael Borodiansky

----- Original Message -----
From: "Daniel F. Savarese" <dfs@savarese.org>
To: <oro-dev@jakarta.apache.org>
Sent: Friday, March 30, 2001 12:45 AM
Subject: Re: Question:


>
> >Let R1 be the regular expression 1
> >Let R2 be the regular expression 2
> >
> >R1 < R2 iff all inputs that R1 can match R2 can, but not vice versa.
>
> Although an interesting question, it doesn't have much to do with the
> development of the jakarta-oro software and should probably be
> directed to a mailing list or newsgroup on lexical analysis.  However,
> I will venture to say it is a solvable problem for DFA and even some
> NFA representations of regular expressions, but not for Perl5
> expressions.  You have to be able to compute closures and show that
> the closure of R2 over all of its inputs is a superset of the closure
> of R1, which is straightforward for DFAs.
>
> daniel
>
>


Mime
View raw message