# Automata

## 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}$ $\epsilon$ $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 $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:

There are tentative definitions of

higher dimensional automaton?

which take a more nPOV of automata theory.

## References

category: computer science

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