# Morphism of automata category

What is the typed morphism in category $\mathcal{A}$ of finite automata? Let $\mathcal{G}$ be a category of oriented graphs. Does $\mathcal{A}$ equivalent to $\mathcal{C}$

-
It would help if you included definitions of these categories. –  Qiaochu Yuan Aug 22 '13 at 5:52
I cant find defenition of automata categroy. I know that we can define equivalent of two automatas $A,B$ (i.e. isomorphism in $\mathrm{Hom}(A,B)$?), cartesian product of two automatas. Its typical category theory defenition. –  burder Aug 22 '13 at 6:12
As to definitions category of automata, see, e.g., M.Arbib, Arrows, structures and functors. –  Boris Novikov Aug 22 '13 at 7:38
Many thanks, Boris Novikov. –  burder Aug 22 '13 at 8:03

## 1 Answer

There are many ways to define morphisms between automata, but here is one which is useful. Let $\mathcal{A}_1 = (Q_1, A, \cdot_1, i_1, F_2)$ and $\mathcal{A}_2 = (Q_2, A, \cdot_2, i_2, F_2)$ be two complete DFA. A morphism from $\mathcal{A}_1$ to $\mathcal{A}_2$ is a surjective function $f: Q_1 \to Q_2$ such that $f(i_1) = i_2$, $f^{−1}(F_2) = F_1$ and, for all $a \in A$ and $q \in Q$, $f(q\cdot a) = f(q)\cdot a$. This is the correct way to define the minimal automaton of a language (as a final object). See Chapter 3 in

S. Eilenberg, Automata, languages, and machines Vol. A, Academic Press, New York, 1974. Pure and Applied Mathematics, Vol. 58.

Eilenberg actually gives a more general definition of morphisms for incomplete automata.

-