Thank you for your input, Mike. I was hoping an implementor like you would
comment on the issues.
I came to Kelvin's conclusions on my own last night, namely
- 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.
- Intersection means taking the cross-product of the NDFA's state
space. This is blowup. Is it significant in practice?
This doesn't seem too horrible. So what's the problem?
One thing seems clear -- to do intersection and complement, we'd have
to extend the interface to the underlying matching engine.
-Olin
|