Redirected from Finite state automaton
There are several types of finite state machines:
Acceptors produce a "yes or no" answer to the input; either accepting the input or not. Recognizers categorise the input. 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 nondeterministic automata. In deterministic automata, for each state there is at most one transition for each possible input. In nondeterministic automata, there can be more than one transition from a given state for a given possible input. Nondeterministic automata are usually implemented by converting them to deterministic automata  in the worst case, the generated deterministic automaton is exponentially bigger than the nondeterministic automaton (although it can usually be substantially optimised).
The standard acceptance condition for nondeterministic automata 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).
Mealy machines have actions (outputs) associated with transitions and Moore machines have actions associated with states.

Formally, a deterministic finite automaton (DFA) consists of
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 set of strings it accepts form a language, which is the language the DFA recognises.
The following example explains a deterministic finite state machine with a binary alphabet, which determines if the input contains an even number of 0s.
Simply put, the state S_{1} represents that there has been an even number of 0s in the input so far, while S_{2} signifies an odd number. A 1 in the input does not change the state of the automaton. When the input ends, the state will show whether the input contained an even number of 0s or not.
A nondeterministic finite automaton (NFA) consists of
The machine starts in all of the start states and reads in a string of symbols from its alphabet. It uses the transition relation T to determine the next state(s) using the current state(s) 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 set of strings it accepts form a language, which is the language the NFA recognises.
Optimization and Canonicalisation
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 computationally powerful machines. Furthermore, it is possible to construct a canonical version of any FSM, in order to test for equality. Both of these problems can be solved using a colouring algorithm.
FSMs can only recognize regular languages, and hence they are less computationally powerful than Turing machines  there are decidable problems that are not computable using a FSM.
For each nondeterministic FSM a deterministic FSM of equal computational power can be constructed with an algorithm.
A FSM may be represented using a state transition table or a state diagram.
Implementation A finite state machine can be implemented in software with a state transition matrix (in some cases a sparse matrix[?] implemented with linked lists or a huge switchstatement for detecting the internal state and then individual switch statements for decoding the input symbol.
In hardware a FSM may be built from a programmable logic device.
See also
Search Encyclopedia

Featured Article
