Finite-state automaton
From Esolang
A finite-state automaton, abbreviated FSA, is a simple form of imaginary machine. It is also sometimes referred to as a finite-state machine, finite automaton, or finite-state transducer.
Contents |
[edit] Definition
(Note: FSAs are employed for various purposes - recognizing formal languages, modelling the dynamic behaviour of systems, etc. - and such applications often use marginally different definitions appropriate to their problem domain. We'll try to use a very general definition on this page, and then describe the common variations.)
At any given time, a FSA can be in any one of a finite number of states. It receives input signals from an outside source, one by one. As each signal is received, the FSA transitions to another (possibly the same) state, based on the input signal and the FSA's current state. When there are no further input signals to be processed, the FSA can be considered to be left in a final state.
A FSA may also be considered to produce output signals which are directed towards some external sink. It may produce these when a particular transition occurs (as in a Mealy machine) or when a particular state is reached (as in a Moore machine.) (These two situations are equivalent save for the number of states required.) Output signals may be of the same, or different, nature as the input signals.
A FSA can be considered to be able to produce more than one output signal per transition or state. Or, some transitions may not depend on an input signal at all, moving to a new state automatically. (These two situations are also equivalent, save for the number of states required.)
All states have a transition for all possible input signals. If an input signal is considered 'illegal' it cannot be rejected - the FSA must still transition to some state. This is often handled by having a non-accepting state which is transitioned to from all states by an 'illegal' input signal, and from which the FSA can never 'escape'. This state is often left out of diagrams and is simply implied.
The actions of an FSA may be deterministic or non-deterministic; a non-deterministic FSA accepts an input if there is some path of choices leading to an accepting state. For recognisers there is an algorithm to remove nondeterminism, but often greatly increasing the number of states.
[edit] Depiction
FSAs can be depicted as transition tables, or more intuitively, as directed graphs where vertices are states and edges are transitions from state to state. Edges are annotated with the input signal on which the transition occurs. Output signals can be notated either on edges, on vertices, or both.
[edit] Language recognition
For the purposes of a recognizing a string to be part of a formal language such as a regular expression, the signals are the symbols of the string, and the final state determines whether the FSA "accepts" the string or not - i.e., whether the formal language associated with the FSA includes that string. An FSA of this kind would typically generate no output, but merely finish in an 'accept' or 'reject' state, and is known as an acceptor or recogniser.
FSAs are powerful enough to recognize some sets of strings, but not others. For example, it is possible to construct a FSA which can tell you whether or not a string starts with an opening parenthesis and ends with a closing parenthesis, no matter how long that string is. No FSA can tell you, however, whether those parentheses are correctly nested - for that, you need a push-down automaton.
[edit] Computational power
A FSA has a small, but not insignificant, amount of computational power - as much as it takes to recognize a regular expression, as noted above. It can, for example, add two integers of unbounded extent.
Many more powerful computational models turn out to be computationally equivalent to FSAs when trivial restrictions are placed on them. For example, a Turing machine which can only move right is computationally equivalent to a FSA.
Several esoteric programming languages fall into the same computational class as FSAs.
