uses for state machines

Question

In what areas of programming would I use state machines ? Why ? How could I implement one ?

EDIT: please provide a practical example , if it's not too much to ask .

Solution 1

In what areas of programming would I use a state machine?

Use a state machine to represent a (real or logical) object that can exist in a limited number of conditions ("states") and progresses from one state to the next according to a fixed set of rules.

Why would I use a state machine?

A state machine is often a very compact way to represent a set of complex rules and conditions, and to process various inputs. You'll see state machines in embedded devices that have limited memory. Implemented well, a state machine is self-documenting because each logical state represents a physical condition. A state machine can be embodied in a tiny amount of code in comparison to its procedural equivalent and runs extremely efficiently. Moreover, the rules that govern state changes can often be stored as data in a table, providing a compact representation that can be easily maintained.

How can I implement one?

Trivial example:

enum states {      // Define the states in the state machine.
  NO_PIZZA,        // Exit state machine.
  COUNT_PEOPLE,    // Ask user for # of people.
  COUNT_SLICES,    // Ask user for # slices.
  SERVE_PIZZA,     // Validate and serve.
  EAT_PIZZA        // Task is complete.
} STATE;

STATE state = COUNT_PEOPLE;
int nPeople, nSlices, nSlicesPerPerson;

// Serve slices of pizza to people, so that each person gets
/// the same number of slices.   
while (state != NO_PIZZA)  {
   switch (state)  {
   case COUNT_PEOPLE:  
       if (promptForPeople(&nPeople))  // If input is valid..
           state = COUNT_SLICES;       // .. go to next state..
       break;                          // .. else remain in this state.
   case COUNT_SLICES:  
       if (promptForSlices(&nSlices))
          state = SERVE_PIZZA;
        break;
   case SERVE_PIZZA:
       if (nSlices % nPeople != 0)    // Can't divide the pizza evenly.
       {                             
           getMorePizzaOrFriends();   // Do something about it.
           state = COUNT_PEOPLE;      // Start over.
       }
       else
       {
           nSlicesPerPerson = nSlices/nPeople;
           state = EAT_PIZZA;
       }
       break;
   case EAT_PIZZA:
       // etc...
       state = NO_PIZZA;  // Exit the state machine.
       break;
   } // switch
} // while

Notes:

• The example uses a switch() with explicit case/break states for simplicity. In practice, a case will often "fall through" to the next state.

• For ease of maintaining a large state machine, the work done in each case can be encapsulated in a "worker" function. Get any input at the top of the while(), pass it to the worker function, and check the return value of the worker to compute the next state.

• For compactness, the entire switch() can be replaced with an array of function pointers. Each state is embodied by a function whose return value is a pointer to the next state. Warning: This can either simplify the state machine or render it totally unmaintainable, so consider the implementation carefully!

• An embedded device may be implemented as a state machine that exits only on a catastrophic error, after which it performs a hard reset and re-enters the state machine.

Solution 2

Some great answers already. For a slightly different perspective, consider searching a text in a larger string. Someone has already mentioned regular expressions and this is really just a special case, albeit an important one.

Consider the following method call:

very_long_text = "Bereshit bara Elohim et hashamayim ve'et ha'arets." …
word = "Elohim"
position = find_in_string(very_long_text, word)

How would you implement find_in_string? The easy approach would use a nested loop, something like this:

for i in 0 … length(very_long_text) - length(word):
    found = true
    for j in 0 … length(word):
        if (very_long_text[i] != word[j]):
            found = false
            break
    if found: return i
return -1

Apart from the fact that this is inefficient, it forms a state machine! The states here are somewhat hidden; let me rewrite the code slightly to make them more visible:

state = 0
for i in 0 … length(very_long_text) - length(word):
    if very_long_text[i] == word[state]:
        state += 1
        if state == length(word) + 1: return i
    else:
        state = 0
return -1

The different states here directly represent all different positions in the word we search for. There are two transitions for each node in the graph: if the letters match, go to the next state; for every other input (i.e. every other letter at the current position), go back to zero.

This slight reformulation has a huge advantage: it can now be tweaked to yield better performance using some basic techniques. In fact, every advanced string searching algorithm (discounting index data structures for the moment) builds on top of this state machine and improves some aspects of it.

Solution 3

What sort of task?

Any task but from what I have seen, Parsing of any sort is frequently implemented as a state machine.

Why?

Parsing a grammar is generally not a straightforward task. During the design phase it is fairly common that a state diagram is drawn to test the parsing algorithm. Translating that to a state machine implementation is a fairly simple task.

How?

Well, you are limited only by your imagination.

I have seen it done with case statements and loops.

I have seen it done with labels and goto statements

I have even seen it done with structures of function pointers which represent the current state. When the state changes, one or more function pointer is updated.

I have seen it done in code only, where a change of state simply means that you are running in a different section of code. (no state variables, and redundent code where necessary. This can be demonstrated as a very simply sort, which is useful for only very small sets of data.

int a[10] = {some unsorted integers};

not_sorted_state:;
    z = -1;
    while (z < (sizeof(a) / sizeof(a[0]) - 1)
    {
        z = z + 1
        if (a[z] > a[z + 1])
        {
            // ASSERT The array is not in order
            swap(a[z], a[z + 1];        // make the array more sorted
            goto not_sorted_state;      // change state to sort the array
        }
    }
    // ASSERT the array is in order

There are no state variables, but the code itself represents the state

Solution 4

The State design pattern is an object-oriented way to represent the state of an object by means of a finite state machine. It usually helps to reduce the logical complexity of that object's implementation (nested if's, many flags, etc.)

Solution 5

If you're using C#, any time you write an iterator block you're asking the compiler to build a state machine for you (keeping track of where you are in the iterator etc).

View more solutions

Comments

[Jasper Bekkers]

Downside of that pattern is that it has the potential to add an explosive number of classes to your project, making it unclear what exactly goes on and what the flow of the state transitions is.

[Nemanja Trifunovic]

Exactly. Besides, I find graphs a much better way to describe a FSM than UML

[Jasper Bekkers]

It's kinda strange though, seeing how FSMs are such an important part of quite a lot of fields (game AI for example) you'd think someone would've come up with a decent solution?

[Adam Liss]

My pleasure. Note there is no check for division by zero. If you have no friends, you should spend more time away from StackOverflow. :-)

[Konrad Rudolph]

Jasper, there are several solutions which are more than just decent. It's just that because of the diversity of fields, these solutions have very different requirements. One implementation doesn't fit all. Personally, I've used everything from OOP & graphs over switchs to bit operations for FSMs.

[AmitaiB]

+1 for putting the ghost in the machine! (Though I wonder why you left out an apostrophe in 'hashamayim', but not 'ha'aretz' ;)

[Konrad Rudolph]

@AmitaiB I have to admit that I don’t actually know any ancient Hebrew, I just knew the first few words, googled the phrase and copied the first result. :-p

[user1459144]

Great Example! Could you please elaborate how can you get better performance with state machine approach ?

[OpalApps]

The link to your framework implementation points at an empty directory. Were the sources moved somewhere?

[Charles Duffy]

@OpalApps The directory isn't empty if you use bzr to clone it; there's just nothing displayed in a conventional web browser. bzr itself is dead, but there's a still-maintained fork, en.m.wikipedia.org/wiki/Breezy_(software)

[Charles Duffy]

@OpalApps, ...that said, in the years since I've mirrored it to GitHub; github.com/charles-dyfis-net/isg-state-machine-framework

[Charles Duffy]

That said, the open source release doesn't include any of the screen scrapers that were built on top of that framework, but only the framework itself.

[OpalApps]

yes, found it. Thanks for the clarifications.