Finite automata (also known as finite-state machines) are a compact way of encoding the order in which events should occur. An automaton is a set of state nodes with transitions between nodes being prompted by events.
Finite automata have applications in parsing, token recognition, protocol handling, and other areas. More powerful automata have code associated with each state node, which is executed when the node position is reached. Examples include the automata generated by yacc and its ilk.
There are two main types of finite automaton:
- deterministic — each event transition from a state node is unique, and every transition has an event associated with it. The current traversal state is completely described by a single node position within the automaton.
- non-deterministic — there can be more than one transition for a particular event from a particular state node, or there are transitions without an event. The current traversal state is described by a set of possible node positions within the automaton.
To traverse a deterministic automaton, you simply keep track of which node you're at, and follow the transition from that node for the next event. It's easy to tell when you've received an invalid event (there are no transitions from the current node), and to tell when you've finished (the current node is the finish state node).
Traversing a non-deterministic automaton involves the following:
1. tracking all the viable node positions within the automaton
2. advancing from each of these node positions for an event, and across any transitions without an event
You can tell when an invalid event has been received because there are no elements remaining in the set of viable node positions. "Finished," however, can mean one of two things:
a) The set of viable node positions contains the finish state node at any point in the series of events.
b) The series of events has ended and the finish state node is in the set of viable node positions.
Which of these definitions of "finished" should be used depends on the application. o