What kind of problems are state machines good for? [closed]

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

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 2

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.