What kind of problems are state machines good for?

Question

What kind of programming problems are state machines most suited for?

I have read about parsers being implemented using state machines, but would like to find out about problems that scream out to be implemented as a state machine.

Answer 1

Stateful protocols such as TCP are often represented as state machines. However it's rare that you should want to implement anything as a state machine proper. Usually you will use a corruption of one, i.e. have it carrying out a repeated action while sitting in one state, logging data while it transitions, or exchanging data while remaining in one state.

Answer 2

Workflow (see WF in .net 3.0)

Answer 3

They have many uses, parsers being a notable one. I have personally used simplified state machines to implement complex multi-step task dialogs in applications.

Answer 4

A parser example. I recently wrote a parser that takes a binary stream from another program. The meaning of the current element parsed indicates the size/meaning of the next elements. There are a (small) finite number of elements possible. Hence a state machine.

Answer 5

They're great for modelling things that change status, and have logic that triggers on each transition.

I'd use finite state machines for tracking packages by mail, or to keep track of the different stata of a user during the registration process, for example.

As the number of possible status values goes up, the number of transitions explodes. State machines help a lot in that case.

Answer 6

Things that comes to mind are:

• Robot/Machine manipulation... those robot arms in factories
• Simulation Games, (SimCity, Racing Game etc..)

Generalizing: When you have a string of inputs that when interacting with anyone of them, requires the knowledge of the previous inputs or in other words, when processing of any single input requires the knowledge of previous inputs. (that is, it needs to have "states")

Not much that I know of that isn't reducible to a parsing problem though.

Answer 7

AI in games is very often implemented using State Machines. Helps create discrete logic that is much easier to build and test.

Answer 8

Objects in games are often represented as state machines. An AI character might be:

• Guarding
• Aggressive
• Patroling
• Asleep

So you can see these might model some simple but effective states. Of course you could probably make a more complex continuous system.

Another example would be a process such as making a purchase on Google Checkout. Google gives a number of states for Financial and Order, and then informs you of transistions such as the credit card clearing or getting rejected, and allows you to inform it that the order has been shipped.

Answer 9

Regular expression matching, Parsing, Flow control in a complex system.

Regular expressions are a simple form of state machine, specifically finite automata. They have a natural represenation as such, although it is possible to implement them using mutually recursive functions.

State machines when implemented well, will be very efficient.

There is an excellent state machine compiler for a number of target languages, if you want to make a readable state machine.

http://research.cs.queensu.ca/~thurston/ragel/

It also allows you to avoid the dreaded 'goto'.

Answer 10

Just as a side note, you can implement state machines with proper tail calls like I explained in the tail recursion question.

In that exemple each room in the game is considered one state.

Also, Hardware design with VHDL (and other logic synthesis languages) uses state machines everywhere to describe hardware.

Answer 11

A good resource is this free State Machine EBook. My own quick answer is below.

When your logic must contain information about what happened the last time it was run, it must contain state.

So a state machine is simply any code that remembers (or acts on) information that can only be gained by understanding what happened before.

For instance, I have a cellular modem that my program must use. It has to perform the following steps in order:

1. reset the modem
2. initiate communications with the modem
3. wait for the signal strength to indicate a good connection with a tower
4. ...

Now I could block the main program and simply go through all these steps in order, waiting for each to run, but I want to give my user feedback and perform other operations at the same time. So I implement this as a state machine inside a function, and run this function 100 times a second.

enum states{reset,initsend, initresponse, waitonsignal,dial,ppp,...}
modemfunction()
{
  static currentstate

  switch(currentstate)
  {
  case reset:
    Do reset
    if reset was successful, nextstate=init else nextstate = reset
    break
  case initsend
    send "ATD"
    nextstate = initresponse 
    break
  ...
  }
currentstate=nextstate
}

More complex state machines implement protocols. For instance a ECU diagnostics protocol I used can only send 8 byte packets, but sometimes I need to send bigger packets. The ECU is slow, so I need to wait for a response. Ideally when I send a message I use one function and then I don't care what happens, but somewhere my program must monitor the line and send and respond to these messages, breaking them up into smaller pieces and reassembling the pieces of received messages into the final message.

Answer 12

If you need a simple stochastic process, you might use a Markov chain, which can be represented as a state machine (given the current state, at the next step the chain will be in state X with a certain probability).

Answer 13

Any workflow application, especially with asynchronous activities. You have an item in the workflow in a certain state, and the state machine knows how to react to external events by placing the item in a different state, at which point some other activity occurs.

Answer 14

The easiest answer is probably that they are suited for practically any problem. Don't forget that a computer itself is also a state machine.

Regardless of that, state machines are typically used for problems where there is some stream of input and the activity that needs to be done at a given moment depends the last elements seen in that stream at that point.

Examples of this stream of input: some text file in the case of parsing, a string for regular expressions, events such as player entered room for game AI, etc.

Examples of activities: be ready to read a number (after another number followed by a + have appear in the input in a parser for a calculator), turn around (after player approached and then sneezed), perform jumping kick (after player pressed left, left, right, up, up).

Answer 15

The concept of state is very useful for applications to "remember" the current context of your system and react properly when a new piece of information arrives. Any non trivial application has that notion embedded in the code thru variables and conditionals.

So if your application has to react differently every time it receives a new piece of information because of the context you are in, you could model your system with with a state machines. An example would be how to interpret the keys on a calculator, which depends on what your are processing at that point in time.

On the contrary, if your computation does not depend of the context but solely on the input (like a function adding two numbers), you will not need an state machine (or better said, you will have a state machine with zero states)

Some people design the whole application in terms of state machines since they capture the essential things to keep in mind in your project and then use some procedure or autocoders to make them executable. It takes some paradigm chance to program in this way, but I found it very effective.