(Maybe off topic) Can someone explain what a finite state machine is?

Terry Reedy tjreedy at udel.edu
Tue Jul 19 19:49:02 CEST 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 mailing list