当时这两颗变成紫色或绿色的灿烂星宿,想必也在闪烁吧。

Let’s consider the alphabet Σ={a,b}\Sigma=\{a,b\}, and C,D\mathcal{C},\mathcal{D} are two categories.

C\mathcal{C} is:

1

What really matters is:

Deterministic Finite Machine, DFA, can be regarded as the functor from monoid (List(Σ),[],++)(List(\Sigma),[],++) to the category of sets.

In fact, since HomSet(List(Σ)×S,S)HomSet(Σ×S,S)Hom_{Set}(List(\Sigma)\times S,S)\stackrel{\cong}{\rightarrow}Hom_{Set}(\Sigma\times S,S), so we can think the functor from C\mathcal{C} to Set.

For example, consider the DFA:

3

it can be regarded as the functor XX:
4

X(Δ)=The  set  of  states  X(a)=δaX(b)=δbX(\Delta)=The\;set\;of\;states\;\\ X(a)=\delta_a\\ X(b)=\delta_b

Obviously it’s a functor from C\mathcal{C} 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:

5

They work equivalently, since we can merge state 1A,1B,1C1A,1B,1C and 2A,2B2A,2B in DFA YY.

That means we have a natural transformation YXY\rightarrow X.

Consider the two diagrams:

6

where

X(Δ)={0,1,2}Y(Δ)={0,1A,1B,1C,2A,2B}X(\Delta)=\{0,1,2\}\\ Y(\Delta)=\{0,1A,1B,1C,2A,2B\}

We can guarantee that there exists a function α:{0,1A,1B,1C,2A,2B}{0,1,2}\alpha:\{0,1A,1B,1C,2A,2B\}\rightarrow\{0,1,2\} making two diagrams commute.

In this example, α\alpha is quite obvious:

α(0)=0α(1A)=α(1B)=α(1C)=1α(2A)=α(2B)=2\alpha(0)=0\\ \alpha(1A)=\alpha(1B)=\alpha(1C)=1\\ \alpha(2A)=\alpha(2B)=2

Then the diagram commute:

αY(a)(1A)=α(2A)=2X(a)α(1A)=δa(1)=2\alpha\circ Y(a)(1A)=\alpha(2A)=2\\ X(a)\circ\alpha(1A)=\delta_a(1)=2