ANML Documentation

Non-Deterministic Finite Automata versus Deterministic Finite Automata

One additional distinction that sets automata apart from traditional state machines is that automata are non-deterministic, meaning multiple states can be active simultaneously.

The current posture in most academic institutions is that non-deterministic finite automata (NFAs) should be converted to deterministic finite automata (DFAs), and then the DFAs can be implemented in whatever medium the designer is using. This NFA-to-DFA conversion, however, can suffer from state-space explosion where an exponential number of states and transitions are required to represent all of the state and transition possibilities expressed compactly in the NFA. By natively supporting NFA implementations, Automata Processor designs are not subject to this state-space explosion issue.

See Deterministic and Non-Deterministic Finite Automata for more information.