On Wed, 15 Dec 2004, David E. Wheeler wrote:
I guess that makes it a DFA, no?
Yes, but not in the traditional sense. Traditionally, you can only have 1 transition from a state for a given input. i.e. the model all by itself defines a deterministic behavior. What you actually have is model+algorithm defining a deterministic behavior.
IMHO, I would simply disallow multiple transitions in the model, which would make it a real DFA. This change shouldn't impact your algorithm. (i.e. it's doesn't find the *first* match, but rather *the* match.)
I'm pretty sure you don't want to try to implement an NFA directly. You'd have to explore each possible transition (and following transitions), backtracking when you reach a dead end. It would be better to convert an NFA into a DFA. (NFAs are equivalent in power to DFAs.)
David
_____________________________________________________________________ David Coppit [EMAIL PROTECTED] The College of William and Mary http://coppit.org/
"Government big enough to supply everything you need is big enough to take everything you have ... The course of history shows that as a government grows, liberty decreases." -- Thomas Jefferson
