In article <qijbuaxbn7l.fsf@lambda.ai.mit.edu>,
Olin Shivers <shivers@ai.mit.edu> wrote:
> - Complement means just complementing accept/non-accept states
> in the NDFA. No blowup in NDFA space at all. How this affects
> state count in the result DFA compared to the original DFA,
> I don't know.
If you have complement, you have intersection, by DeMorgan's law.
So the effect of complement on complexity is at least as bad as
that of intersection. The algorithm you gave for complement
doesn't work for syntax-directed translation to NFA's. I.e. it
works for complementing the whole r.e. but does not work for
complementing a subexpression. I think the way to do it for a
subexpression might be to include an e-transition from every
node of the subexpression *except* its accepting states, to the
following node after the subexpression. The problem is that
e-transitions in the subject NFA themselves could do funny
things to your complement algorithm. I'd have to think about it
carefully, I'm awfully rusty, and I don't really have time.
> - Intersection means taking the cross-product of the NDFA's state
> space. This is blowup. Is it significant in practice?
Actually intersection is cross products of DFA's. This clearly
works. Taking a cross product of NFA's is a bit nebulous
because of e-transitions. You could build NFA's without
e-transitions, I think cross products of those would work as
well. A DFA is O(2**n), and an NFA without e-transitions is
O(n^2). So you may be talking at least O(n**4) complexity for
intersections. Assuming this naive algorithm really works. It
also has similar difficulties for syntax directed translation
(i.e. you can't).
|