uses for state machines [closed]

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 .

Answer 1

State machines are everywhere. State machines are key in communications interfaces where a message needs to be parsed as it is received. Also, there have been many times in embedded systems development that I've needed to separate a task into multiple tasks because of strict timing constraints.

Answer 2

Finite state machines can be used for morphological parsing in any natural language.

Theoretically, this means that morphology and syntax are split up between computational levels, one being at most finite-state, and the other being at most mildly context sensitive (thus the need for other theoretical models to account for word-to-word rather than morpheme-to-morpheme relationships).

This can be useful in the area of machine translation and word glossing. Ostensibly, they're low-cost features to extract for less trivial machine learning applications in NLP, such as syntactic or dependency parsing.

If you're interested in learning more, you can check out Finite State Morphology by Beesley and Karttunen, and the Xerox Finite State Toolkit they designed at PARC.

Answer 3

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.

Answer 4

A typical use case is traffic lights.

On an implementation note: Java 5's enums can have abstract methods, which is an excellent way to encapsulate state-dependent behavior.

Answer 5

A lot of digital hardware design involves creating state machines to specify the behaviour of your circuits. It comes up quite a bit if you're writing VHDL.

Answer 6

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