Tuesday, 25 October 2011

Finite State Machine in C

Finite State Machine is a way of modelling behaviour of some entity that can have a (finite) set of states. Depending on the received event, entity performs some action and changes its state (or remains in the current one).

Let's say we want to model a behaviour of some simple car. I call it "simple" as it has only ignition switch, accelerator and brake. Driver can turn it on, then accelerate, brake and, at the end of the journey, turn it off. If not careful, driver can break the car - if tries to turn it on (again) while driving. Driver's actions are events - inputs of our model. Car can be turned off, idling, moving or broken - and this is a set of our car's states. So, car is in some state, it reacts on driver's command (event), performs some action and goes into the next state.

We have a finite set of states and events and can draw a diagram which precisely define state transitions (state transition diagram):


Now, how to implement this model and show how this state machine changes states after receiving events?

Each state can be represented as unique number - its code, or ID. The similar thing is with events. As we have finite number of both states and events, we can use enum type to represent them: one variable will be of enum STATE type and contain the ID of the current state and another variable will be of type enum EVENT and will contain the most recent event this system received. Initially, our car is turned off so the state variable will be set to STATE_TURNED_OFF. After this simple initialization we just need to wait for events and handle them in accordance to the given transition diagram. Events can be obtained from a keyboard or some other source and they are usually kept in a queue as sometimes a new event can be received before processing of the previous one is finished. In this example, in order to keep things simple, I'm gonna assume that processing is fast enough and will just create a predefined set of events and put them in an array.

As we have repetitive action - receiving and handling events - we'll put it in a loop. If our events source is keyboard and we don't know how many events will user issue, we can use while-loop and CTRL-C as a loop termination command. In this example, we have an array of events which is of predefined (known in advance) size so we can use for-loop. Inside this loop, we need to place event processing code for each event, received in each state. This means we will have switch-statement inside another switch-statement. So, here's the code:



Whoooa! I'm turned on!
Yipee! I'm accelerating!
Whoops! Was I too fast?
That was probably enough...

Having a switch inside a switch looks a bit complex and difficult to maintain. If we add a new state, we need to add a new case-branch for each event. In the code above it would mean we need to make changes at 4 different places in the code! Not good!

A solution for this is a state transition table. It is basically a table in which each state has its column and each event has its row. Table elements are pairs action/next-state - let's put them in some structure called TRANSITION. If transition table is called trans_tbl its element, trans_tbl[evt][state] is of type TRANSITION and action is a function called during transition and next-state is the state our model goes into for the current event. Code tells this better:


Output is the same:

Whoooa! I'm turned on!
Yipee! I'm accelerating!
Whoops! Was I too fast?
That was probably enough...

The code has shrunk and become easier to understand and maintain: if we want to add a new event or a state, we just need to change transition table (trans_tbl) - we don't need to touch the code in a loop!

My article "Finite State Machine in C++" shows how to use OOP and State design pattern in order to implement FSM described here.

Links and references:
Finite-state machine (Wikipedia)
UML Tutorial: Finite State Machines


Unknown said...

Very informative. Thanks

Unknown said...

its really very helpful for beginner

micheal pan said...

BE SMART AND BECOME RICH IN LESS THAN 3DAYS....It all depends on how fast 
you can be to get the new PROGRAMMED blank ATM card that is capable of
hacking into any ATM machine,anywhere in the world. I got to know about 
this BLANK ATM CARD when I was searching for job online about a month 
ago..It has really changed my life for good and now I can say I'm rich and 
I can never be poor again. The least money I get in a day with it is about 
$50,000.(fifty thousand USD) Every now and then I keeping pumping money 
into my account. Though is illegal,there is no risk of being caught 
,because it has been programmed in such a way that it is not traceable,it 
also has a technique that makes it impossible for the CCTVs to detect 
you..For details on how to get yours today, email the hackers on : (
atmmachinehackers1@gmail.com ). Tell your 
loved once too, and start to live large. That's the simple testimony of how 
my life changed for good...Love you all ...the email address again is ;