Finite-state automaton

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.

Definition

(Note: FSAs are employed for various purposes - recognizing formal languages, modelling the dynamic behaviour of systems, representing entities in video games, 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 can be in several states at once; it 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 (at most 2ⁿ, where n is the number of states in the non-deterministic automaton).

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.

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 (which regular expressions can't tell either) - for that, you need a push-down automaton.

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.

Many esoteric programming languages fall into the same computational class as FSAs.

History

Systems which could transition between a finite number of internal states have been known of for a long time, but it was not until relatively late in the early history of computer science that they were formally studied.

The following quotes are from Rabin and Scott[1959, "Finite automata and their decision problems," IBM Journal of Research and Development 3,2 (April, 1959), 114]:

"Turing machines are widely considered to be the abstract prototype of digital computers; workers in the field, however, have felt more and more that the notion of a Turing machine is too general to serve as an accurate model of actual computers. It is well known that even for simple calculations it is impossible to give an a priori upper bound on the amount of tape a Turing machine will need for any given computation. It is precisely this feature that renders Turing's concept unrealistic."

"In the last few years the idea of a finite automaton has appeared in the literature. These are machines having only a finite number of internal states that can be used for memory and computation. The restriction of finiteness appears to give a better approximation to the idea of a physical machine. Of course, such machines cannot do as much as Turing machines, but the advantage of being able to compute an arbitrary general recursive function is questionable, since very few of these functions come up in practical applications."