Let’s consider the alphabet , and are two categories.
What really matters is:
Deterministic Finite Machine, DFA, can be regarded as the functor from monoid to the category of sets.
In fact, since , so we can think the functor from to Set.
For example, consider the DFA:
it can be regarded as the functor :
Obviously it’s a functor from to Set, although only one of the sets is involved
Then what would happen if two DFAs work equivalently?
Two DFAs accept the same language if and only if there exists a natural transformation.
Example: consider the two DFAs as following:
They work equivalently, since we can merge state and in DFA .
That means we have a natural transformation .
Consider the two diagrams:
We can guarantee that there exists a function making two diagrams commute.
In this example, is quite obvious:
Then the diagram commute: