uses for state machines [closed]
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 explicitcase/breakstates for simplicity. In practice, acasewill often "fall through" to the next state.For ease of maintaining a large state machine, the work done in each
casecan be encapsulated in a "worker" function. Get any input at the top of thewhile(), 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.
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.
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
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.)