(Maybe off topic) Can someone explain what a finite state machine is?
tjreedy at udel.edu
Tue Jul 19 13:49:02 EDT 2011
On 7/19/2011 9:32 AM, Matty Sarro wrote:
> Hey everyone. I am currently reading through an RFC, and it mentions
> that a client and server half of a transaction are embodied by finite
> state machines. I am reading through the wikipedia article for finite
That was going to be my first suggestion, but I see that it is flagged
as possibly confusing. You *might* find the article on Turing machines
more helpful, as they are finite-state machines that compute, and the
base model for digital (as opposed to analog) computers.
> state machines, and sadly it's going a bit above my head. I don't
> really have a background in engineering, and would really love to
> understand what is being said. Does anyone have a simple way to
> explain it?
You did not say what background you do have, so I will assume you are
familiar with cars and light switches. The piston chamber in a car
engine has several continuous variables. Temperature, pressure,
concentration of nitrogen, oxygen, fuel, and combustion products, and
position and velocity of the piston. It is a continuous-state machine.
A lamp switch, on the other hand, is the simplest-possible useful finite
state machine. It has two states (on and off) and just one input
(rotate) that switches between the two. A vertically mounted wall light
switch has two inputs (push-up and push-down) that each either switch
the state or leave it the same.
Back to cars. The transmission is a finite-state machine. It has a small
finite set of gear settings: P, R, N, D, D2, L (for one example). The
inputs are pushes (push right-left, up-down, or maybe both) on a gear
stick that either switches to another state or stays in the original
state. Ignition key settings are similar. In modern cars, the two are
interlinked. For automatic transmissions, there is the additional
complication that switching from N to D while stationary actually
switches from N to L, and gear switch inputs are generated by the car as
well as by the driver.
The common feature of finite state machines are finite sets of states,
inputs, and outputs. Inputs may cause a switch to another state and an
output. Another everyday example: a house door can be open, closed,
locked, dead-bolted, or both, and maybe barred. There are input actions
but no outputs, unless the door is hooked to an alarm system, which is
another finite-state system.
Terry Jan Reedy
More information about the Python-list