SPLat Logo

Finite State Machines - Make light work of complex functions

NOTICE: We are updating our website. For product enquiries and orders please contact us directly.
NOTICE: SPLat Controls has moved. We are now at 1/85 Brunel Rd, Seaford, 3198. map

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 HelpTip?

Maybe you are programming one of the following:

  • Machine controllersHelpTip
  • Robotics
  • Games programsHelpTip
  • Transaction processingHelpTip
  • Communications protocols
  • Puzzle solversHelpTip

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. HelpTip.

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.

Next >

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.

EC1 Controller

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!...