On Dec 15, 2004, at 11:27 AM, David E. Wheeler wrote:
On Dec 15, 2004, at 6:34 AM, Orton, Yves wrote:
As far as I know a DFA is defined as a finite automaton where each
state/input combination can result in only one legal transition.
(http://en.wikipedia.org/wiki/Finite_state_machine) An NFA of course can
have multiple transitions for a given state/input combination. (You can see
this definition in regards to determinisitc turing machines and non
deterministic turing machines in the wikipedia article as well.)
Based on this definition, I'm not sure if my module is a DFA or an NFA state machine. In each state, you can define rules for transitioning to other states. When you call the check() method, it checks each of these in the order you defined them and transitions to the first state for which the rule evaluates to a true value. This means that multiple rules could evaluate to a true value, but since it short-circuits and there is no backtracking, technically only one transition can occur.
It short-circuits and there's no backtracking? That's odd. Seems like that should be stated in the docs somewhere, since that's how most people expect an FSA to work.
In any case, in order to be a DFA, it must satisfy the following conditions:
1) Mutually exclusive set of transitions away from any node (which you basically satisfy by only using the first match)
2) Every transition must "consume some input". For pattern-matching, this means every transition steps forward through the target string, but since the transitions in your module are arbitrary and user-defined, it seems like one could easily create a machine where this (or an analog of it) isn't necessarily true.
So it looks like you've got NFAs (or just FSAs, if you prefer), not DFAs.
-Ken
