State Machines are not difficult! - A FSM tutorial
By David Stonier-Gibson, SPLat Controls
Do you need an easy way make your programs respond to events or user actions in ways that can vary depending on past
events, or history 
?
Maybe you are programming one of the following:
- Machine controllers
- Robotics
- Games programs
- Transaction processing
- Communications protocols
- Puzzle solvers
The Finite State Machine (FSM for short, sometimes called Finite State Automaton) is a programming technique that can handle such situations very easily.
The most complicated aspect of finite state machines is the name itself.
.
The way I am going to do this is first of all to introduce you to a diagram that describes a finite state machine. That is in many ways the
most important part, because it gives you a very powerful design tool. Then I will show you how to translate a
State Diagram into program code. About 20 minutes from now you will have a powerful new tool in your programming arsenal.
Stop press
Since I wrote this tutorial we have developed a FSM design and programming tool that represents FSMs as a table. This is an
alternative way of looking at them, and for some people may be easier. The tool is called Tabula™. It can be
used to design and specify FSM programs for any platform, and also to generate programs for our embedded controller.
Visit the Tabula FSM programming page
Buy a SPLat for $29.00
Program your own Finite State Machine using a SPLat Controller for only $29.00.
The EC1 "EasyOne", a 32-bit fully featured SPLat Controller with
USB and true multi-tasking is a easy way to learn and a cheap way to build your project.
Take for example a program for cash withdrawal from an ATM. The customer needs to
be guided through a series of steps that direct them to the final goal. Along the
way there are many things that can go wrong and need to be corrected, so the process
has "side branches". At each point the transaction is therefore in a unique "state".
The ATM's response to the various buttons varies dramatically according to the current state.
Using a Finite State machine design for such a programming task will cut it right down
to size and make it perfectly manageable.
There is also a bonus: Designing the program for an ATM is going to involve a team of
stake holders, who all need to know it is going to work properly, and reliably. With FSMs
there is a diagram, called a state diagram, which shows the full logic in a way that
even non-programmers can understand. So here the FSM has become not only a programming
tool but a powerful communications tools as well.
Some classes of puzzle lend themselves to solutions based on FSM concepts. This is where
the word "finite" comes in. Some puzzles have a relatively small number of
possible states, like the "Missionaries and Cannibals problem". Many many years
ago I wrote a solver for that puzzle using state concepts. Games like chess have a finite
number of states, but the number is so large that a state machine solution is not practical
in present-day memory sizes.
Nevertheless, just thinking about a puzzle in terms of states and state transitions can be
very helpful.
Click to see the missionaries and cannibals puzzle.
Games programs are a dead sitter for FSMs. In games you frequently have on-screen
characters whose behaviour must be relevant to the past history of the game. That
knowledge of past history is represented by the "state" of the character.
It is easy to represent the state of a character as a single number. When an event
occurs in the game, that number can be used to select the appropriate reaction or action.
In some cases the program's response to an event under one set of conditions
can be the total opposite of the response under different conditions. For
example, when you play a movie clip on your computer there is a button on
the player that can pause or resume the playback (totally opposite responses),
depending on what it is already doing.
This covers a huge range of applications. Anything that involves reacting
to inputs, sequencing outputs, and timing according to a set of rules can
be considered machine control. Examples are:
- Pallet wrapper
- Air conditioner
- Dish washer
- Aquarium
- Grey water system
- Trash compactor, garbage truck
- Autoclave
- Palletiser
- Dairy equipment
- Energy management system
- Conveyors
- Bottling and packaging equipment
In fact, I am not even going to try and explain the name, for fear of losing
you before we even get started. By the time this is over you will pretty much
have it figured out for yourself
Talking of of losing the audience, the formal, mathematical definition of an
FSM is such brain numbing, eye popping mumbo jumbo I feel certain that 9 out
of 10 electronic engineering and IT students switch off in the first 5 minutes
of the FSM lecture series, never to ever benefit from the power of FSMs in their
work.
This is not difficult stuff, it's just made to look difficult by the academics!
Click now if you want your brain numbed and your eyes popped!...
