Finite state machine

A finite state machine (FSM) is an abstract machine used in the study of computation and languages. There are several types of finite state machines: some are used to recognize languages (deterministic and non-deterministic finite automata), whilst others are used to generate an output string given an input string (??? and Mealey machines).

A deterministic finite automata (DFA) is an alphabet (Sigma), 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 * Sigma -> 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. NFAs are equivalent in power to DFAs, but are easier to construct. An NFA can be converted to a DFA by the subset construction.

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.