nLab
automaton

Idea

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

Definition

An automaton is formally definable as in Joy of Cats as a sextuple ($Q$, $\Sigma$, $Y$, $\delta$, $q_0$, $y$), where $Q$ is the set of states, $\Sigma$ and $Y$ are the sets of input symbols and output symbols, respectively, $\delta$: $\Sigma$ $\times$ $Q$ $\to$ $Q$ is the transition map, $q_0$ $ϵ$ $Q$ is the initial state, and $y$: $Q$ $\to$ $Y$ is the output map. Morphisms from an automaton ($Q$, $\Sigma$, $Y$, $\delta$, $q_0$, $y$) to an automaton ($Q$′, $\Sigma$′, $Y$′, $\delta$′, $q_0$′, $y$′) are triples ($f_Q$, $f_{\Sigma }$, $f_Y$) of functions $f_Q:Q\to Q\prime$, $f_{\Sigma }:\Sigma \to \Sigma \prime$, and $f_Y:Y\to Y\prime$ satisfying the following conditions:

(i) preservation of transition: $\delta \prime$($f_{\Sigma }$($\sigma$), $f_Q$($q$)) = $f_Q$($\delta$($\sigma$, $q$)),

(ii) preservation of outputs: $f_Y$($y$($q$)) = $y$$\prime$($f_Q$($q$)),

(iii) preservation of initial state: $f_Q$($q_0$) = $q_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 $f$ : ($Q$, $\delta$, $q_0$, $F$) $\to$ ($Q\prime$, $\delta \prime$, $q_0\prime$, $F\prime$) (called a simulation) is a function $f:Q\to Q\prime$ that preserves:

(i) the transitions, i.e., $\delta \prime$($\sigma$, $f$($q$)) = $f$($\delta$($\sigma$, $q$)),

(ii) the initial state, i.e., $f$($q_0$) = $q_0\prime$, and

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

The category of automata

There is a category $\mathrm{Aut}$ 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:

• asynchronous automaton;

• deterministic automaton;

• nondeterministic automaton.

There are tentative definitions of

higher dimensional automaton?

which take a more nPOV of automata theory.

References

• Jiri Adamek, Horst Herrlich, and George Strecker, Abstract and concrete categories: the joy of cats. free online

• Mark V. Lawson, Finite automata, CRC Press, see also here.

category: computer science