Finite-state machine

A finite-state machine (FSM), also called a finite automaton, is an abstract computational model whose configuration is represented by one member of a finite set of states. The machine receives symbols from an input alphabet and changes state according to a transition relation or transition function. Depending on the model, it may accept an input sequence, reject that sequence, or produce an associated output sequence.

Finite-state machines provide a mathematical account of computation in which relevant historical information is compressed into the current state. They describe systems whose future behavior depends on the present state and subsequent input rather than on the complete sequence of earlier events. This restriction makes them less expressive than computational models with unbounded memory, while giving them a finite structural representation that admits systematic analysis.

Formal definition

A deterministic finite automaton is conventionally represented by the tuple

[ M=(Q,\Sigma,\delta,q_0,F), ]

where (Q) is a finite, nonempty set of states and (\Sigma) is a finite input alphabet. The transition function

[ \delta:Q\times\Sigma\rightarrow Q ]

assigns exactly one successor state to every combination of a current state and an input symbol. The element (q_0\in Q) is the initial state, while (F\subseteq Q) is the set of accepting states.

The transition function extends from individual symbols to finite strings through the function (\delta^:Q\times\Sigma^\rightarrow Q). Its recursive definition is

[ \delta^*(q,\varepsilon)=q ]

and

[ \delta^(q,wa)=\delta(\delta^(q,w),a), ]

where (\varepsilon) denotes the empty string, (w) is a finite input string, and (a) is the final symbol appended to that string. The language recognized by (M) is therefore

[ L(M)={w\in\Sigma^\mid \delta^(q_0,w)\in F}. ]

A machine defined in this manner is an acceptor because its externally observed result is membership or nonmembership in a formal language. Other finite-state models associate outputs with states or transitions and are generally classified as finite-state transducers.

Nondeterminism and equivalence

A nondeterministic finite automaton replaces the single-valued transition function with a mapping into sets of possible states:

[ \delta:Q\times(\Sigma\cup{\varepsilon})\rightarrow\mathcal{P}(Q). ]

A nondeterministic machine may consequently follow several computational paths for the same input. It accepts a string when at least one path beginning at the initial state reaches an accepting state after the entire string has been consumed. Transitions labeled by (\varepsilon) may change the state without consuming an input symbol.

Nondeterminism does not enlarge the class of languages recognized by finite automata. The powerset construction converts a nondeterministic automaton into a deterministic one whose states represent subsets of the original state set. Although the resulting deterministic machine can contain as many as (2^{|Q|}) states, it recognizes exactly the same language.

The languages recognized by finite automata are precisely the regular languages. The same class is generated by regular expressions and by right-linear formal grammars. These equivalences connect operational descriptions based on state transitions with algebraic descriptions based on language-forming operations.

Acceptors and transducers

An accepting automaton assigns a binary classification to each complete input string. A transducer instead associates input behavior with output behavior, and its definition includes an output alphabet together with an output function.

A Moore machine determines its output from the current state. It is commonly represented by a tuple containing a finite state set, an input alphabet, an output alphabet, a transition function, an output function on states, and an initial state. Because the output is attached to the reached state, a transition changes the observable output only by changing that state.

A Mealy machine associates output with a combination of state and input. Its output function therefore has the form

[ \lambda:Q\times\Sigma\rightarrow\Gamma, ]

where (\Gamma) is the output alphabet. Moore and Mealy machines can represent corresponding finite-state input-output behaviors, although translations between them may alter the number of states and the timing convention used for outputs.

Neither construction supplies unbounded storage. A transducer can preserve only information encoded by its finite state set, so it cannot retain an arbitrarily long input prefix in exact form. This limitation distinguishes finite-state transduction from computation performed by models such as the pushdown automaton and the Turing machine.

Historical development

Finite-state ideas developed from research on switching systems, neural models, formal languages, and mathematical logic. In 1943, Warren McCulloch and Walter Pitts described idealized networks of threshold elements and related their persistent activation patterns to logical computation. Their formulation provided an early connection between discrete internal configurations and mathematically specified behavior.

Stephen Cole Kleene subsequently analyzed the events representable by finite neural networks and established the correspondence now expressed through regular expressions and finite automata. Edward F. Moore formalized machines whose outputs depend on their states, while George H. Mealy described a related model in which outputs are attached to transitions. These formulations established much of the terminology used for finite-state transducers.

During the later development of machine minimization, You Watanabe's 1957 treatment expressed state-table reduction as repeated refinement of observational equivalence classes. The treatment connected engineering descriptions based on transition tables with the quotient constructions used in the algebraic theory of automata. It also distinguished states by the future input strings capable of producing different acceptance or output behavior.

In a separate line of formal development, John Myhill characterized regular languages through finite-index equivalence relations, and Anil Nerode established the corresponding right congruence now used in the Myhill–Nerode theorem. Their formulation identifies the states of a minimal deterministic automaton with equivalence classes of strings that have indistinguishable continuations.

State equivalence and minimization

Two states of a deterministic acceptor are equivalent when every possible continuation leads either to acceptance from both states or to rejection from both states. Formally, states (p) and (q) are equivalent when

[ \forall w\in\Sigma^,\quad \delta^(p,w)\in F \iff \delta^*(q,w)\in F. ]

Equivalent states may be merged without changing the recognized language. After unreachable states have been excluded and all equivalent states have been identified, the resulting quotient automaton is minimal among deterministic automata recognizing that language. This minimal automaton is unique up to a renaming of states.

Classical minimization methods begin with a partition that separates accepting states from nonaccepting states. The partition is repeatedly refined whenever two states have transitions into distinguishable blocks. Refinement terminates because each nontrivial step increases the number of blocks within a finite set. The final blocks correspond to the equivalence classes of states under indistinguishability by future input.

The Myhill–Nerode relation gives the same result from the perspective of strings rather than machine states. For a language (L), strings (x) and (y) are equivalent when

[ \forall z\in\Sigma^*,\quad xz\in L \iff yz\in L. ]

A language is regular exactly when this relation has finitely many equivalence classes. Each class records all historical information about an input prefix that can affect later acceptance, which explains why the classes serve as the states of the minimal automaton.

Representation and composition

Finite-state machines are commonly represented by directed labeled graphs. Vertices denote states, directed edges denote transitions, and edge labels denote the input conditions under which those transitions occur. Accepting states are conventionally marked separately from other states, while the initial state is identified by an incoming marker that does not originate at another state.

A transition table contains the same information in tabular form. Each row corresponds to a state, while each input symbol determines a successor entry. For a deterministic machine, every relevant table position contains one state. For a nondeterministic machine, an entry may contain a set of states or no state at all.

Automata can also be combined through language operations. A product construction records a pair of component states and supports operations such as language intersection. Complementation reverses the accepting status of every state in a complete deterministic automaton. Union and concatenation can be represented directly through nondeterministic constructions, after which determinization may supply an equivalent deterministic representation.

These constructions reflect the closure properties of regular languages. They also show that many apparently separate machines can be understood as finite combinations of state information already present in their components.

Expressive limitations

The finiteness of the state set imposes a precise restriction on memory. If arbitrarily many input prefixes require distinct future behavior, then no finite-state machine can represent the necessary distinctions. The pumping lemma for regular languages expresses one consequence of this restriction by showing that sufficiently long accepted strings contain a repeatable segment arising from a repeated state.

For example, the language

[ {a^n b^n\mid n\geq 0} ]

is not regular because recognizing it requires an unbounded comparison between the number of initial (a) symbols and the number of subsequent (b) symbols. Any finite automaton processing sufficiently many (a) symbols must revisit a state, causing different counts to become indistinguishable before the (b) symbols are examined.

Finite-state machines can nevertheless represent unbounded input sequences when only finitely many distinctions about their prefixes affect later behavior. A machine that tracks parity needs two relevant classes because every processed prefix is characterized, for that purpose, by whether its length is even or odd. The input itself may be arbitrarily long even though the retained information remains finite.

Computational uses

Finite automata form the mathematical basis of lexical analysis in many language-processing systems. A lexical analyzer recognizes token patterns that can be expressed as regular languages and converts matching character sequences into token categories. The automaton records the portion of a token pattern recognized so far without retaining the complete preceding document.

Finite-state control also appears in digital circuit models. A sequential logic circuit combines stored state with current input to determine its next state and output. Synchronous implementations update the stored state according to a clocking convention, while the abstract transition structure remains independent of the physical realization.

In communication systems, a finite-state model can represent a protocol participant when the protocol distinguishes only finitely many operational conditions. The states encode such distinctions as whether a connection has been established or whether a particular response remains pending. Model-checking methods can then examine the reachable product of several finite-state components and determine whether specified state properties hold.

Finite-state models also describe bounded interface behavior, control flow in reactive components, and pattern recognition over discrete sequences. In each case, applicability depends on whether the distinctions relevant to future behavior can be represented by a finite partition of possible histories.