|
|
A finite state machine is a kind of ``black box'' device that responds to external stimuli. Seen from the outside, the device appears as if it can occupy any of a finite number of states; depending on the current state, a given input causes the device to issue a particular output and then enter a new state. Our Fsm's are deterministic in the sense that the current state and the input uniquely determine the output and the new state.
This externally-visible behavior can be conveniently described by means of a state transition diagram. The state transition diagram of Figure 1 describes a vending machine that accepts various coins and button pushes (inputs) and issues various sounds and food products (outputs):
This example is adapted from Wulf, Shaw, Hilfinger, Flon, Fundamental Structures of Computer Science, p.17.
Vending Machine State Transition Diagram
In the diagram, states are denoted by ellipses and transitions are denoted by labeled arcs. A label is an ordered pair giving (1) the input followed by (2) the output associated with the transition.