An automaton is an abstract concept of machine, which consists of states and processes between the states.


An automaton is formally definable as in Joy of Cats as a sextuple (QQ, Σ\Sigma, YY, δ\delta, q 0q_{0}, yy), where QQ is the set of states, Σ\Sigma and YY are the sets of input symbols and output symbols, respectively, δ\delta: Σ\Sigma ×\times QQ \to QQ is the transition map, q 0q_{0} ϵ\epsilon QQ is the initial state, and yy: QQ \to YY is the output map. Morphisms from an automaton (QQ, Σ\Sigma, YY, δ\delta, q 0q_{0}, yy) to an automaton (QQ′, Σ\Sigma′, YY′, δ\delta′, q 0q_{0}′, yy′) are triples (f Qf_{Q}, f Σf_{\Sigma}, f Yf_{Y}) of functions f Q:QQf_{Q}: Q \to Q\prime, f Σ:ΣΣf_{\Sigma}: \Sigma \to \Sigma\prime, and f Y:YYf_{Y}: Y \to Y\prime satisfying the following conditions:

(i) preservation of transition: δ\delta\prime(f Σf_{\Sigma}(σ\sigma), f Qf_{Q}(qq)) = f Qf_{Q}(δ\delta(σ\sigma, qq)),

(ii) preservation of outputs: f Yf_{Y}(yy(qq)) = yy\prime(f Qf_{Q}(qq)),

(iii) preservation of initial state: f Qf_{Q}(q 0q_{0}) = q 0q_{0}\prime.

A deterministic sequential Moore automaton is a finite state automaton where the outputs are determined by the current state alone (and do not depend directly on the input).

A morphism ff : (QQ, δ\delta, q 0q_{0}, FF) \to (QQ\prime, δ\delta\prime, q 0q_{0}\prime, FF\prime) (called a simulation) is a function f:QQf : Q \to Q\prime that preserves:

(i) the transitions, i.e., δ\delta\prime(σ\sigma, ff(qq)) = ff(δ\delta(σ\sigma, qq)),

(ii) the initial state, i.e., ff(q 0q_{0}) = q 0q_{0}\prime, and

(iii) the final states, i.e., f[F]Ff[F] \subseteq F\prime.

The category of automata

There is a category AutAut whose objects are deterministic sequential Moore automata and whose morphisms are simulations.


There are several variant forms of automaton. The above just gives a basic one. Others are treated in the entries:

There are tentative definitions of

higher dimensional automaton?

which take a more nPOV of automata theory.


category: computer science

Revised on September 8, 2012 10:22:14 by Tim Porter (