display | more...
Finite state automata, a.k.a. finite state machines, are used to specify programmed behaviour to sequences of events, or input symbols fed to the automaton.

A finite (state) automaton is a finite directed graph, the nodes of which are interpreted as possible states of affairs; the arrows are possible transitions between these states. Transitions are labeled with events (often called, symbols).

A finite state automaton is deterministic if its transition table is a total function, i.e., if in every state, on every possible input the automaton has exactly one transition defined.

A nondeterministic finite automaton (nfa), on the other hand, can have states in which for some inputs there is more than one transition, or none at all.

The nondeterministic kind doesn't have more expressive power. Proof: consider an nfa's powerset automaton, whose states are defined by all subsets of states in the nfa, and whose transitions are defined by < X, a Y > for all X,Y with an x in X, y in Y such that in the original nfs, a path of 0 or more transitions leads from x to y. This powerset automaton is deterministic and accepts the same strings.

A set has exponentially many subsets, so this can really blow up the size of the automaton. This cannot be avoided: for many classes of nfas, all equivalent dfas are exponentially larger. So nfa are a more much concise notation.

Nfas can be written down as context-free grammars with restricted sets of rules; the so-called regular grammars. In practice, a more popular, and usually more concise, notation for regular languages is the regular expression.

On deterministic automata, the most interesting operation is minimization, which removes the states that are unreachable from the start state. Given a regular language, its minimal dfa is unique up to isomorphism.

DFAs are rather nice for some tasks and when identified can greatly speed up the core of an algorithm. Take for example, the question of "Is a number divisible by 3?" Classically, you would read the entire number into memory, and then divide it by 3. However, this requires that you have memory at least as large as the number. This isn't practical for very large numbers of very small memory.

Consider the following deterministic finite automaton. You start at the > and follow it around. Treat the number you want to test for divisibility by 3 as a binary number e.g '3' is '11', and '4' is '100'. If you end up in a state labeled with '*' you have a number divisible by 3. The number in the state is the modulo of the number. One important concept here is that this takes up only 2 bits of memory to store which state you are in. This can be seen in the four states in the diagram below. Each state could be labed from 0-3 (in binary 00, 01, 10, 11). In this instance, the start state (state 3) is designated 'n' for null.

```        /--\
>| n|
\--/
/    \
0      1
v        v
/-- /--\ <-1-- /--\ <-0-- /--\ --\
0   |*0|       | 1|       | 2|   1
\-> \--/ --1-> \--/ --0-> \--/ <-/
```

To follow this DFA, lets take 9 as an example. One starts in state 'n' with the highest bit. The binary representation would be '1001'. Thus, the first step would be to follow the path from 'n' to '1' along the '1' arrow. From state '1', a '0' leads us to state '2', and the next '0' leads us back to state '1'. The final '1' leads us to state '*0'.

Other common tasks where DFAs live at the core are terminal programs, web servers, and game AI's.

Log in or register to write something here or to contact authors.