DFSA V.S. NDFSA
There are two common forms of State-Machines, the first one is known as the deterministic Finite-State-Automaton, which involves only and only a single a-successor transition path arising from every state; where [a] is the transition input value. Moreover, a transition must be specified for each input value.
- E.g:
Notes:
- Starting states are marked by this arrow
->.- Terminating states (aka. accepting states) are marked by double circles.
- A valid recognizable pattern can be instantiated by starting from an arrow state
->and finishing at a double-circled state.- For a DFSA pattern, the number of starting states is restricted to only one.
- For a DFSA pattern, at least a single state must be specified as an ending state (accepting/terminating).
- For a DFSA pattern, each state can only have a single a-successor transition path; where [a] is the transition input value.
In this example, the following is true:
- State-A has only a single successor transition path of input value [1] pointing to State-B, and a single path of input value [0] pointing to State-C.
- State-B has only a single successor transition path of the input value [0] pointing to State-A, and a single path of input value [1] pointing to another state of B.
- State-C has only a single successor transition path of the input value [0] pointing to a new state of type C, and a single path of input value [1] pointing to a new state of type C.
The second one is known as the non-deterministic Finite-State-Automaton, which involves other alternative ways of defining transition paths including but not limited to, multiple successor paths, and no input value for a transition (null-transitions).
- E.g:
Notes:
- Starting states are marked by this arrow
->.- Terminating states (aka. accepting states) are marked by double circles.
- A valid recognizable pattern can be instantiated by starting from an arrow state
->and finishing at a double-circled state.- For an NDFSA pattern, at least a single state must be specified as a starting state (initiating).
- For an NDFSA pattern, at least a single state must be specified as an ending state (accepting/terminating).
- For an NDFSA pattern, states can have multiple a-successor; where [a] is the input of the transition path.
In this example, the following is true:
- State-A is a starting state, and State-B is an accepting or terminating state.
- State-A has two 1-successor (a successor transition of input value [1]).
- State-B has a single 0-successor pointing to a new state of A.
- This NDFSA pattern is equivalent to the above DFSA.
Examples of the recognizable patterns by this NDFSA:
- 1110, in the following path: > Start -> A -1-> B -1-> D -1-> C -0-> A -> End <
- 11011, in the following path: > Start -> B -1-> D -1-> C -0-> B -1-> D -1-> C -> End <
- 1111, in the following path: > Start -> A -1-> B -1-> A -1-> B -1-> A -> End <
- 11111, in the following path: > Start -> A -1-> B -1-> A -1-> B -1-> D -1-> C -> End <
- 111, in the following path: > Start -> A -1-> B -1-> D -1-> C -> End <
- And so on...
This NDFSA state transition graph rejects the following patterns:
- 100
- 0001
- 1000
- 10000
- 10
- And any other patterns that have invalid paths using this NDFSA.
NDFSA helps to build transition graphs easier, in which any rule can be applied and states can have more than one successor transition of the same input type and even multiple input values.
NDFSA adds the value to easily define recognizable patterns (e.g: a set of strings, or even a set of solutions to a logical system), a recognizable pattern is defined by following one of the valid paths defined by this FSA state diagram, thus a single NDFSA pattern can define a subset of recognizable patterns (think of a game state with a tweakable subset of sequential actions).
On the other hand, DFSA has a verbose and strict logic pattern, however, both provide equivalent values, and conversion between both can be done easily, in the next chapter, we will discuss some good techniques to convert from a NDFSA to a DFSA; because DFSA is direct, verbose and strict and usually simple in its transitions, sometimes it's feasible.