Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Is there an algorithm for regular expression intersection.

6 views
Skip to first unread message

Charles Fiterman

unread,
Sep 12, 2002, 9:55:09 AM9/12/02
to
Does anyone know of an algorithm which will determine if two regular
expressions intersect?

Mark Biggar

unread,
Sep 12, 2002, 10:43:21 AM9/12/02
to
Charles Fiterman wrote:
> Does anyone know of an algorithm which will determine if two regular
> expressions intersect?

Convert both to DFA's, create the intersection DFA, check for empty
(check final state accessability). all those steps can be found in any
automata theory textbook. Unfortunately, this appears to be an
expotential time algorithm because of the first step.

--
Mark Biggar
mark.a...@attbi.com

Matt Timmermans

unread,
Sep 12, 2002, 11:24:14 PM9/12/02
to
"Mark Biggar" <mark.a...@attbi.com> wrote in message
news:3D80A7F2...@attbi.com...

If you don't actually need to calculate the intersection, then you can test
to see if it's non-empty in polynomial time. Just convert each regular
expression into an NFA, and calculate the set of valid NFA state pairs
(A,B), A in regex 1, B in regex 2, reachable by the same string. To
calculate this set, start with the pair of start states and generate the
obvious closure. Iff the pair of terminal states is included in the final
result, then the expressions intersect.


0 new messages