I'm looking for more examples of the following model of state machines:

in David Spivak's book on category theory, he gives in section and in application, a description of a finite state machine in terms of category theory. The basic definition is that you fix an alphabet $\Sigma$ and take the list monoid $\mathcal{M} := (list(\Sigma), ++, [])$, then describe the state machine as a functor $X : \mathcal{M} \to \mathsf{Set}$. Given two state machines $X$ and $Y$ (described as functors), you can talk about "refinement" via natural transformations $\alpha : X \Rightarrow Y$. The story seems to end here.

This is an interesting model of state machines. I've never seen it before, and I am having trouble finding similar descriptions of state machines. I would like to see how far it has been (can be?) extended. E.g., talk about things like bisimulations, language acceptance, turing machines, computability, etc. Does anyone have more sources?

  • $\begingroup$ This is cool. One thing I thought up related to this is that you can define commutativity of diagrams that aren't necessarily DAG. When a loop is present you'd treat it as a DFA. The strings accepted starting in state $X$ and accepting in state $Y$ are composition paths: $f\circ g \circ h \equiv fgh$ so very string-like. Anyway, the language between those two nodes is a language of morphisms, and each one of them are equal. In other words, this generalizes commutativity to a wider range of diagram functors. $\endgroup$ Commented Jun 25, 2023 at 4:50

1 Answer 1


A very similar construction/viewpoint has been recently studied by Colcombet and Petrişan in [CP20]. They see a deterministic finite automaton as a functor $$\mathcal{A} \colon \mathcal{I} \to \mathsf{Set}$$ where $\mathcal{I}$ is the category induced by the three objects $\textsf{initial}$, $\textsf{states}$ and $\textsf{accept}$, whose morphisms are generated by:

  • a morphism $i\colon \textsf{init} \to \textsf{states}$,
  • a morphism $f\colon \textsf{states} \to \textsf{accept}$, and
  • for each letter $a\in\Sigma$, a morphism $a\colon \textsf{states} \to \textsf{states}$.

Moreover, they add the restriction that $\mathcal{A}(\textsf{init})$ has cardinality 1, and $\mathcal{A}(\textsf{final})$ has cardinality 2. This construction is based exactly on the same idea as the one in David Spivak's book, except that his construction cannot specify initial states and final states.

One thing that is quite pleasant with this approach is that you can obtain other classical automata models by changing the category used in the codomain of $\mathcal{A}$ (and the constraints on $\mathcal{A}(\textsf{init})$ and $\mathcal{A}(\textsf{final})$). For instance, non-deterministic automata are obtained by considering the category $\mathsf{Rel}$, and weighted-automata over a field $\mathbb{K}$ by taking the category of $\mathbb{K}$-vector spaces.

A soft introduction to [CP20] can be found in [slides by Petrişan] starting from page 21. However, I do not know of any work modelling a Turing machine (or a machine with the ability to write) using the framework of category theory.


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.