8
$\begingroup$

What does meanthat two finite automata is equivalent? I think that we must define category of finite automata, i.e. we must define $\mathrm{Hom}(A,B)$, where $A,B$ be an arbitrary finite automata. Hence two finite automata $A,B$ are equivalent if there exist isomorphism $f\in\mathrm{Hom}(A,B)$. So, how we can define category of finite automata?

$\endgroup$
5
  • 4
    $\begingroup$ Wanting a notion of equivalence should not suggest that you need to define morphisms. $\endgroup$ Oct 4, 2013 at 6:03
  • 2
    $\begingroup$ The question how to define morphisms for automata is interesting in its own right. $\endgroup$
    – Michael
    Oct 4, 2013 at 6:48
  • 1
    $\begingroup$ It's my impression that most definitions of equivalence involve defining not just when two things are equivalent, but also what it means to specify an equivalence between them, and these equivalences are very likely to form a category, @ScottMorrison. $\endgroup$ Oct 4, 2013 at 12:42
  • 1
    $\begingroup$ @ScottMorrison, I do not understand --- why should not it suggest? Could you explain your claim? $\endgroup$ Oct 11, 2013 at 21:56
  • $\begingroup$ @MichalR.Przybylek At the very least, because equivalence is a symmetric relation and morphisms have no need for symmetry - it might be worth exploring whether an equivalence relation comes from a particularly natural morphism, but there's no reason to believe that it must. $\endgroup$ Jan 28, 2016 at 22:38

2 Answers 2

7
$\begingroup$

You can find these notions, e.g, in the book

Ji.Adamek, V.Trnkova, Automata and Algebras in Categories. Kluwer, 1989,

S.Eilenberg, Automata, languages, and machines, v.A. Academic Press, 1974

and others books. In the first book there is also a more weak notion of equivalence -- automata with the same behavior.

Addendum: Let an automaton (with an initial state) has an input alphabet $A$ and an output alphabet $B$. Then for every word $x\in A^*$ we get in processing the word $y\in B^*$. The map $f:A^*\to B^*, f(x)=y,$ is called a behavior of the automaton. We can consider two automata as equivalent if they have the same behavior.

$\endgroup$
2
  • $\begingroup$ Would you provide a little more details? E.g. What is meant by the same behavior? Does it mean two automata with the same behavior recognize the same language? How about their underline transition graph? What can we say about two automata with the same transition graph but different initial state/accepting(final) states? etc. Thanks. $\endgroup$
    – Nobody
    Oct 4, 2013 at 9:02
  • $\begingroup$ @scaaahu: I added the answer. $\endgroup$ Oct 4, 2013 at 9:41
4
$\begingroup$

The category of automata is discussed in Example 3.3. (3) in:

Adamek, Herrlich, Strecker - Abstract and concrete categories, the Joy of Cats, online.

It also appears in 4K, 5.2, 7.15, 13.13, 15.3, 20H in that book.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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