# PlanetPhysics/Automaton2

A *(classical) automaton, s-automaton* **Failed to parse (unknown function "\A"): {\displaystyle \A}**
, or sequential machine, is defined as a quintuple of sets, , and , and set-theoretical mappings,

where is the set of s-automaton inputs, is the set of states (or the state space of the s-automaton), is the set of s-automaton outputs, is the *transition function* that maps an s-automaton state onto its next state in response to a specific s-automaton input , and is the *output function* that maps couples of consecutive (or sequential) s-automaton states onto s-automaton outputs :

(hence the older name of sequential machine for an s-automaton).

A categorical automaton can also be defined by a commutative square diagram containing all of the above components.

With the above automaton definition(s) one can now also define morphisms between automata and their composition.

A\htmladdnormallink{homomorphism{http://planetphysics.us/encyclopedia/TrivialGroupoid.html} of automata} orautomata homomorphismis a morphism of automata quintuples that preserves commutativity of the set-theoretical mapping compositions of both the transition

function and the output function .

With the above two definitions one now has sufficient data to define the category of automata and automata homomorphisms.

A *category of automata* is defined as a category of quintuples
and
automata homomorphisms **Failed to parse (unknown function "\A"): {\displaystyle h:{\A}_i \rightarrow {\A}_j}**
,
such that these homomorphisms commute with both the transition and the output functions of any automata **Failed to parse (unknown function "\A"): {\displaystyle {\A}_i}**
and **Failed to parse (unknown function "\A"): {\displaystyle {\A}_j}**
.

**Remarks:**

*Automata homomorphisms*can be considered also as automata transformations

or as semigroup homomorphisms, when the state space, , of the automaton is defined
as a *semigroup* .

- Abstract automata have numerous realizations in the real world as : machines, robots, devices,

computers, supercomputers, always considered as *discrete* state space sequential machines.\\

- Fuzzy or analog devices are not included as standard automata.
- Similarly,
*variable (transition function)*automata are not included, but Universal Turing machines are.

An alternative definition of an automaton is also in use:

as a five-tuple , where is a non-empty set of symbols
such that one can define a *configuration* of the automaton as a couple
of a state and a symbol . Then
defines a "next-state relation, or a transition relation" which associates to each configuration
a subset of S- the state space of the automaton.
With this formal automaton definition, the *category of abstract automata* can be defined by specifying automata homomorphisms in terms of the morphisms between five-tuples representing such abstract automata.

A special case of automaton is that of astable automatonwhen all its state transitions arereversible; then its state space can be seen to possess a groupoid (algebraic) structure. Thecategory of reversible automatais then a 2-category, and also a subcategory of the 2-category of groupoids, or the groupoid category.

An alternative definition of an automaton is also in use:

as a five-tuple , where is a non-empty set of symbols
such that one can define a *configuration* of the automaton as a couple
of a state and a symbol . Then
defines a "next-state relation, or a transition relation" which associates to each configuration
a subset of S- the state space of the automaton.
With this formal automaton definition, the *category of abstract automata* can be defined by specifying automata homomorphisms in terms of the morphisms between five-tuples representing such abstract automata.

A special case of automaton is that of a *stable automaton* when all its state transitions are *reversible* ; then its state space can be seen to possess a groupoid (algebraic) structure. The *category of reversible automata* is then a 2-category, and also a subcategory of the 2-category of groupoids, or the groupoid category.