nLab
automaton

Automata

Idea

An automaton is an abstract concept of machine, modelled as a collection of states and transitions between states, together with an assignment of some external behavior (typically input and/or output) to these transitions. A quintessential example of an automaton is a vending machine, which can be in any number of different states (e.g., “READY”, “INSERT 2 TOKENS”, “OUT OF SERVICE”, etc.), and will transition between these states in response to user input (e.g., from “READY” to “INSERT 2 TOKENS” after the user makes a selection, and from “INSERT 2 TOKENS” to “INSERT 1 TOKEN” after the user inserts a token).

Many different notions of automaton exist in the literature. For now this article only considers one fairly basic notion taken from Joy of Cats, although it is by no means the simplest nor the most general.

Definition

A deterministic, sequential, Moore 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.

Note that in such an automaton, 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.

Variants

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.

References

category: computer science

Revised on May 2, 2014 02:31:47 by Noam Zeilberger (213.111.4.73)