Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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}$

share|cite|improve this question
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

There are many ways to define morphisms between automata; here is one which is useful. Let $\mathcal{A}_1 = (Q_1, A, \cdot_1, i_1, F_1)$ 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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.