Re: NFA and negation/conjunction

Stefan Monnier <monnier@iro.umontreal.ca> writes:


> I'm looking for any work that tries to provide negation and/or
> conjunction operations in regexps without using a DFA (or at least
> while avoiding the DFA state explosion problem).


I assume you mean intersection when you say conjunctipon.


> My search has currently come up empty (actually I pretty much haven't
> seen mention of conjunction and negation in regexps other than in
> Brzozowski's derivatives). So any pointer would be welcome,


You can do intersection of epsilon-free NFAs using the construction
that you use for DFAs (constructing a product automaton). If you just
do a single intersection, this stays quadratic, but multiple
intersections gets exponential. This can't be avoided, as deciding
emptyness of the intersection of a set of regexps is PSPACE complete
in the combined size of the regexps. Since deciding emptyness is
linear in teh size of an automaton, you can't construct an automaton
faster.


Complement of complete DFAs (i.e., DFAs without undefined transitions)
is trivial: You just negate the accepting-state bit. If your DFA is not
complete, it is easy to make it so (just add a dead state and make all
undefined transitions go to this). But I don't think there is a
sub-exponential complement construction for regexps or NFAs.


Torben

Return to the comp.compilers page.
Search the comp.compilers archives again.