Christopher Smith wrote:
Hmm... I can't think of how one might do the NDFA/DFA proof
A DFA can always be constructed from an NDFA.
What they omit is the fact that said DFA may be *huge*. A DFA, may in
fact, be exponential ( O(2^n) ) with respect to the number of states of
the NDFA.
I'm pretty sure that Mastering Regular Expressions has a couple of
examples that will tie a DFA-based regex engine into knots while the
NDFA-based regex engine laughs or just chews for a while and returns an
answer.
The tradeoff if that once you get a DFA out of a regex engine, you
*know* that the machine will complete in linear time with respect to the
number of states.
With an NDFA-based regex engine, you have no knowledge about how long it
will take.
certainly your typical Haskell or ML compiler can verify the equivalence
of a transform.
There's a whole bunch of theoretical math folks who wish that were true...
Even checking the equivalence of two VLSI state machines (very
structured, well-defined, etc.) is O(n^2) or worse (normally much
worse). Actually returning useful information about *where* those
things differ always much worse than O(n^2) (normally O(2^n), IIRC).
-a
--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
