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 (, , , , , ), where is the set of states, and are the sets of input symbols and output symbols, respectively, : is the transition map, is the initial state, and : is the output map. Morphisms from an automaton (, , , , , ) to an automaton (′, ′, ′, ′, ′, ′) are triples (, , ) of functions , , and satisfying the following conditions:
(i) preservation of transition: ((), ()) = ((, )),
(ii) preservation of outputs: (()) = (()),
(iii) preservation of initial state: () = .
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 : (, , , ) (, , , ) (called a simulation) is a function that preserves:
(i) the transitions, i.e., (, ()) = ((, )),
(ii) the initial state, i.e., () = , and
(iii) the final states, i.e., .
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.