Finite state machine
From open-encyclopedia.com - the free encyclopedia.
In the theory of computation, a finite state machine (FSM) or finite state automaton (FSA) is an abstract machine that has only a finite, constant amount of memory. The internal states of the machine carry no further structure. This kind of model is very widely used in the study of computation and languages.
| Contents |
Overview
It can be represented using a state diagram. There are finitely many states, and each state has transitions to states. There is an input string that determines which transition is followed (some transitions may be from a state to itself). Finite state machines are studied in automata theory, a subfield of theoretical computer science.
There are several types of finite state machines including
- Acceptors: they either accept the input or do not.
- Recognizers: they either recognize the input or do not.
- Transducers: they generate output from given input.
Acceptors and recognizers can be treated as the same type.
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 exactly one transition for each possible input (DFA). In non-deterministic automata, there can be none or more than one transition from a given state for a given possible input (NFA, GNFA). 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 non-deterministic automata requires that some computation accepts the input. Alternating automata also provide a dual notion, where for acceptance all non-deterministic 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 machines and Mealy machines).
Mealy machines have actions (outputs) associated with transitions and Moore machines have actions associated with states.
Types of machines
Acceptors and recognizers
- Deterministic finite state machine
- Nondeterministic finite state machine
- Two-way finite state machines
- Generalized nondeterministic finite state machine
Transducers
Optimization and canonicalization
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.
Computational power
FSMs can only recognize regular languages, and hence they are not Turing-complete.
For each non-deterministic FSM, a deterministic FSM of equal computational power can be constructed with an algorithm.
Implementation
A finite state machine can be implemented in software with a state transition table.
- in some cases a sparse matrix implemented with linked lists or
- a huge switch-statement 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, relays, or even a mechanical cam timer combined with other elements.
More specifically, hardware implementation would require state variables, easily conceptualized as D flip-flops, a block of combinational logic which determines the state transition, and a second block of combinational logic that determines the output of a FSM based on its present state (and input if a Mealy machine). This allows the direct mapping to hardware of the algorthm described by a FSM.
Tools
See also
- Pushdown automaton
- Turing machine
- Petri net
- Simulation
- Marvin Minsky
- Automata analyzer
- Coverage analysis
- Transition system
- Protocol development
- Automaton
- Abstract state machine
- Automata theory
References
- Tiziano Villa: Synthesis of Finite State Machines: Functional Optimization, Kluwer Academic Publishers, ISBN 0792398424
- Tiziano Villa: Synthesis of Finite State Machines: Logic Optimization, Kluwer Academic Publishers, ISBN 0792398920
External links
bg:Краен автомат cs:KoneÄný automat de:Endlicher Automat es:Autómata finito fr:Machine à états finis ru:Конечный автомат fi:Äärellinen automaatti zh:有限状态自动机
