|RegEx: AND operator email@example.com (jan) (2003-10-12)|
|Re: RegEx: AND operator firstname.lastname@example.org (2003-10-13)|
|Re: RegEx: AND operator email@example.com (2003-10-13)|
|Re: RegEx: AND operator firstname.lastname@example.org (2003-10-14)|
|Re: RegEx: AND operator email@example.com (Clint Olsen) (2003-10-14)|
|Re: RegEx: AND operator firstname.lastname@example.org (jan) (2003-10-18)|
|Re: RegEx: AND operator email@example.com (jan) (2003-10-19)|
|From:||firstname.lastname@example.org (Aki Helin)|
|Date:||13 Oct 2003 15:26:14 -0400|
|Organization:||Oulun Puhelin Oyj - Baana|
|Posted-Date:||13 Oct 2003 15:26:14 EDT|
jan <email@example.com> wrote:
> The algorithms for translation of regex into NFA are popular; however,
> in none have I seen support for the AND (&) operator.
This is usually called the intersection. Regular languages are closed
under this (and just about any other) operation, so there must be a
NFA for each A & B.
> implemented as another NFA that is run in the required range
> (eg. regex (a.* & ~abc)+ would make one NFA (a.*)+ and for each
> matched (a.*) it would test the other NFA: ~abc) but that's not a good
> solution, besides it won't allow creating NFA. Anybody can help?
If A and B are regular expressions, you could for example compile both
of them to DFAs. Then by making a new DFA where each state is a cartesian
product of the states of DFAs of A and B, you can easily make an automata
that will accept a string if and only if both A and B accept it.
Return to the
Search the comp.compilers archives again.