Finite state machine

A finite state machine (FSM) or finite state automaton (FSA) is an abstract machine used in the study of computation and languages that has only a finite, constant amount of memory (the state). There are several types of finite state machines: finite state acceptors or recognizers are used to recognize languages, whilst finite state transducers are used to generate an output from a given input. Finite automata may operate on languages of finite words (the standard case), infinite words ([Rabin automata]?, [Büchi automata]?), or various types of trees ([tree automata]?), to name the most important cases. A further distinction is between deterministic and non-deterministic automata. While only deterministic automata can be implemented directly, it is often easier to define a nondeterministic automation for a given purpose. The standard acceptance condition for nondetermination requires that some computation accepts the input. [Alternating automata]? also provide a dual notion, where for acceptance all nondeterministic computations must accept.

Apart from theory finite state machines occur also in hardware circuits, where the input, the state and the output are bit vectors of fixed size (Moore and Mealy machines).

Formally, a deterministic finite automaton (DFA) consists of an alphabet (Σ), a set of states (S), one of which is chosen as a start state and zero or more as accepting states, and a transition function (T : S × Σ -> S). The machine starts in the start state and reads in a string of symbols from its alphabet. It uses the transition function T to determine the next state using the current state and the symbol just read. If when it has finished reading it is in an accepting state it is said to accept the string, otherwise it is said to reject the string. The strings it accept form a language, which is the language the DFA recognizes.

A non-deterministic finite automata (NFA) is like a deterministic finite automata, except it permits multiple start states, multiple transitions leaving a state with the same label, and transitions with no label. A NFA accepts a string if there is some sequence of transitions that reads the string and leads from a start state to an accepting state. NFAs are equivalent in power to DFAs, since any NFA can be converted to a DFA by the subset construction. However in general this leads to a number of states in the DFA that is exponential in the number of states of the NFA.

The problem of optimizing an FSM (finding the machine with the least number of states that performs the same function) is decidable, unlike the same problem for more powerful machines.

FSMs can only recognize regular languages, and hence they cannot be used for general computation, unlike Turing machines.