<p>First a clarification about the universal property of the minimal automaton. The minimal automaton <span class="math-container">$M$</span> for a given language is not terminal among all DFAs recognizing the language, since some of those DFAs will contain unreachable states that do not necessarily map in a unique way to the states of <span class="math-container">$M$</span>. Something Eilenberg established in that chapter of his book (Theorem 5.5) is that the minimal complete automaton of a language is a terminal object in a certain category of complete <em>accessible</em> automata, that is, complete DFAs where every state is reachable from the initial state.</p>
<p>There is another perspective on minimization, under which the minimal automaton arises by first passing to a larger category of not necessarily finite automata for a language <span class="math-container">$L$</span>.  This category has an initial object given by the automaton <span class="math-container">$M_0$</span> with state set <span class="math-container">$\Sigma^*$</span>, transition function <span class="math-container">$\delta(w,a) = wa$</span>, initial state <span class="math-container">$i = \epsilon$</span> and set of accepting states <span class="math-container">$F = L$</span>; and a terminal object given by the automaton <span class="math-container">$M_1$</span> with state set <span class="math-container">$2^{\Sigma^*}$</span>, transition function <span class="math-container">$\delta(X,a) = a^{-1}X = \{w \mid aw \in X\}$</span>, initial state <span class="math-container">$i = L$</span> and set of accepting states <span class="math-container">$F = \{X \mid \epsilon \in X\}$</span>.  Then the minimal automaton for <span class="math-container">$L$</span> arises by <em>factoring</em> the unique morphism <span class="math-container">$M_0 \to M_1$</span> as an epimorphism followed by a monomorphism.  For more on this perspective, see</p>
<ul>
<li>Thomas Colcombet and Daniela Petrişan, <em>Automata minimization: a Functorial Approach</em>, LMCS 16:1, 2020 <a href="https://arxiv.org/abs/1712.07121" rel="nofollow noreferrer">arXiv:1712.07121</a></li>
</ul>
<p>In particular this paper models automata abstractly as functors <span class="math-container">$\mathcal{I} \to \mathcal{C}$</span> from an &quot;input category&quot; <span class="math-container">$\mathcal{I}$</span> to some target category <span class="math-container">$\mathcal{C}$</span>.  By choosing <span class="math-container">$\mathcal{C}$</span> appropriately and taking natural transformations between functors as morphisms one recovers categories of different kinds of automata, including both deterministic automata (<span class="math-container">$\mathcal{C} = Set$</span>) and non-deterministic automata (<span class="math-container">$\mathcal{C} = Rel$</span>).  In the latter case the target category does not have a suitable factorization system and so you cannot perform minimization.</p>
<p>On the other hand, it indeed makes sense to consider the powerset construction as building a universal morphism from a NFA to a DFA.  One possible appropriate notion of morphism to consider (corresponding to natural transformations of functors into <span class="math-container">$Rel$</span>) is <em>forward-and-backward simulation</em> <span class="math-container">$M_1 \not\to M_2$</span>: a relation <span class="math-container">$R\subseteq Q_1\times Q_2$</span> on the state sets of the automata, such that for every letter <span class="math-container">$a\in \Sigma$</span>,</p>
<ul>
<li><span class="math-container">$q_1 \to_a q_1'$</span> and <span class="math-container">$(q_1',q_2') \in R$</span> implies there exists <span class="math-container">$q_2$</span> such that <span class="math-container">$(q_1,q_2) \in R$</span> and <span class="math-container">$q_2 \to_a q_2'$</span>, and</li>
<li><span class="math-container">$(q_1,q_2) \in R$</span> and <span class="math-container">$q_2\to_a q_2'$</span> implies there exists <span class="math-container">$q_1'$</span> such that <span class="math-container">$q_1\to_a q_1'$</span> and <span class="math-container">$(q_1',q_2') \in R$</span>.</li>
</ul>
<p>More discussion of the universal property of determinization of NFA without <span class="math-container">$\epsilon$</span>-transitions under different possible scenarios is discussed in this recent paper:</p>
<ul>
<li>Thea Li, <em>Fibrational perspectives on determinization of finite-state automata</em>, ACT 2024, <a href="https://arxiv.org/abs/2410.00675" rel="nofollow noreferrer">arXiv:2410.00675</a></li>
</ul>
<p>The appropriate definition of morphism between <span class="math-container">$\epsilon$</span>-NFA is not entirely clear to me, though I think one possibility that may work for determinization is to consider forward-and-backward simulations under relations that are downwards-closed under <span class="math-container">$\epsilon$</span>-transitions on the left and upwards-closed on the right (i.e., if <span class="math-container">$(q_1,q_2) \in R$</span> and <span class="math-container">$q_1' \to_\epsilon q_1$</span> and <span class="math-container">$q_2 \to_\epsilon q_2'$</span> then <span class="math-container">$(q_1',q_2') \in R$</span>).</p>

CC BY-SA 4.0
2024-11-18T10:02:38.873Z
Wow this is very detailed! Thanks!
Nicola Gigante
CC BY-SA 4.0
2024-11-18T21:33:54.803Z
I’m looking at your answer in detail. What’s the relationship between this “forward-and-backward simulation” and standard bisimulation? There is a similarity (!) between the definitions but I can’t see if they are equivalent.
Nicola Gigante
CC BY-SA 4.0
2024-11-18T22:24:21.783Z
they are not equivalent, probably the best way to see it is to define them in terms of [relational composition](https://en.wikipedia.org/wiki/Composition_of_relations). Let $\delta_a^1 \subseteq Q_1\times Q_1$ and $\delta_a^2 \subseteq Q_2\times Q_2$ be the respective transition relations over a letter $a$. A relation $R \subseteq Q_1\times Q_2$ is a forward-and-backward simulation if $\delta_a^1; R = R;\delta_a^2$ for all $a$, and a bisimulation if $\delta_a^1 ; R \subseteq R ; \delta_a^2$ and $\delta_a^1 ; R^\top \subseteq R^\top ; \delta_a^2$ (writing $R^\top$ for the transpose relation).
Noam Zeilberger
CC BY-SA 4.0
2024-11-18T22:25:56.587Z
observe that bisimulation is a symmetric relation (if $M_1 \times M_2$ then $M_2 \sim M_1$), but forward-and-backward simulation is not.
Noam Zeilberger
CC BY-SA 4.0
2024-11-18T23:38:13.443Z
I kind of screwed up the definition of bisimulation above: it should say $R ; \delta_a^2 \subseteq \delta_a^1 ; R$ and $R^\top ; \delta_a^1 \subseteq \delta_a^2 ; R^\top$.  Concretely that asserts that if $(q_1,q_2) \in R$, then: i) $q_2 \to_a q_2'$ implies there exists $q_1'$ such that $q_1 \to_a q_1'$ and $(q_1',q_2') \in R$, and ii) $q_1 \to_a q_1'$ implies there exists $q_2'$ such that $q_2 \to_a q_2'$ and $(q_1',q_2') \in R$.
Noam Zeilberger
CC BY-SA 4.0
2024-11-18T23:38:55.633Z
If you take $R \subseteq Q \times P(Q)$ to be the membership relation, you can check it defines a forward-and-backward simulation between a NFA and its powerset DFA, but not a bisimulation because condition (i) does not hold: it is possible that $q$ is contained in some set of states $X$ such that $X \to_a X'$, but there is no $q' \in X'$ such that $q \to_a q'$.
Noam Zeilberger
CC BY-SA 4.0
2024-11-20T06:09:53.357Z
Wow the last comment is nailing exactly what I was trying to do with bisimulations but failed (and so I asked the question). Thanks!
Nicola Gigante
CC BY-SA 4.0
2024-11-20T08:18:39.677Z
yeah, I don't know if the existence of a forward-and-backward simulation but not a bisimulation between a NFA and its determinization is well-known, but it was interesting to me when I learned it from Thea Li.
Noam Zeilberger
CC BY-SA 4.0
2024-11-17T09:20:06.393Z
2024-11-17T09:36:04.660Z
2024-11-17T09:36:04.660Z
Noam Zeilberger
<p><a href="https://math.stackexchange.com/a/473412">This answer</a> on Math.SE points to a sound definition of morphisms between DFAs, tracing back to Eilenberg's book.</p>
<p>However, I may be missing something, but the book does not explain why it restricts this notion to DFAs, what breaks on NFAs, and how, if at all, one can define morphisms on NFAs or even on <span class="math-container">$\varepsilon$</span>-NFAs.</p>
<p>What I would actually need is a sound notion of morphisms (by sound I mean suitable to define a category) between <span class="math-container">$\varepsilon$</span>-NFAs (or NFAs, at least) such that minimal DFAs are still terminal objects (although maybe not the only ones). I suppose such a notion should be a proper generalization of what Eilenberg showed, in the sense that a morphism exists between two <span class="math-container">$\varepsilon$</span>-NFAs that happen to be DFAs iff one exists in Eilenberg's sense. I also suspect that such a notion should be such that there's always a morphism between an <span class="math-container">$\varepsilon$</span>-NFA and its powerset DFA.</p>
<p>Maybe I'm missing something trivial but this definition does not seem obvious to me. Is there a way to define any such notion?</p>
<p><strong>In other words</strong>: do <span class="math-container">$\varepsilon$</span>-NFAs form a category with minimal DFAs as terminal objects? What about NFAs?</p>

<reference-request><automata-theory><ct.category-theory>
Morphisms between $\varepsilon$-NFAs
Nicola Gigante
# Morphisms between $\varepsilon$-NFAs

(Asked by: username_0 on 2024-11-07)

[This answer](https://math.stackexchange.com/a/473412) on Math.SE points to a sound definition of morphisms between DFAs, tracing back to Eilenberg's book.

However, I may be missing something, but the book does not explain why it restricts this notion to DFAs, what breaks on NFAs, and how, if at all, one can define morphisms on NFAs or even on $\varepsilon$-NFAs.

What I would actually need is a sound notion of morphisms (by sound I mean suitable to define a category) between $\varepsilon$-NFAs (or NFAs, at least) such that minimal DFAs are still terminal objects (although maybe not the only ones). I suppose such a notion should be a proper generalization of what Eilenberg showed, in the sense that a morphism exists between two $\varepsilon$-NFAs that happen to be DFAs iff one exists in Eilenberg's sense. I also suspect that such a notion should be such that there's always a morphism between an $\varepsilon$-NFA and its powerset DFA.

Maybe I'm missing something trivial but this definition does not seem obvious to me. Is there a way to define any such notion?

**In other words**: do $\varepsilon$-NFAs form a category with minimal DFAs as terminal objects? What about NFAs?

**Tags:** reference-request, automata-theory, ct.category-theory

---

## 1 answers

### Answer by username_1 on 2024-11-17. Score: 4 | Accepted answer

First a clarification about the universal property of the minimal automaton. The minimal automaton $M$ for a given language is not terminal among all DFAs recognizing the language, since some of those DFAs will contain unreachable states that do not necessarily map in a unique way to the states of $M$. Something Eilenberg established in that chapter of his book (Theorem 5.5) is that the minimal complete automaton of a language is a terminal object in a certain category of complete *accessible* automata, that is, complete DFAs where every state is reachable from the initial state.

There is another perspective on minimization, under which the minimal automaton arises by first passing to a larger category of not necessarily finite automata for a language $L$. This category has an initial object given by the automaton $M\_0$ with state set $\Sigma^\*$, transition function $\delta(w,a) = wa$, initial state $i = \epsilon$ and set of accepting states $F = L$; and a terminal object given by the automaton $M\_1$ with state set $2^{\Sigma^\*}$, transition function $\delta(X,a) = a^{-1}X = \{w \mid aw \in X\}$, initial state $i = L$ and set of accepting states $F = \{X \mid \epsilon \in X\}$. Then the minimal automaton for $L$ arises by *factoring* the unique morphism $M\_0 \to M\_1$ as an epimorphism followed by a monomorphism. For more on this perspective, see

* Thomas Colcombet and Daniela Petrişan, *Automata minimization: a Functorial Approach*, LMCS 16:1, 2020 [arXiv:1712.07121](https://arxiv.org/abs/1712.07121)

In particular this paper models automata abstractly as functors $\mathcal{I} \to \mathcal{C}$ from an "input category" $\mathcal{I}$ to some target category $\mathcal{C}$. By choosing $\mathcal{C}$ appropriately and taking natural transformations between functors as morphisms one recovers categories of different kinds of automata, including both deterministic automata ($\mathcal{C} = Set$) and non-deterministic automata ($\mathcal{C} = Rel$). In the latter case the target category does not have a suitable factorization system and so you cannot perform minimization.

On the other hand, it indeed makes sense to consider the powerset construction as building a universal morphism from a NFA to a DFA. One possible appropriate notion of morphism to consider (corresponding to natural transformations of functors into $Rel$) is *forward-and-backward simulation* $M\_1 \not\to M\_2$: a relation $R\subseteq Q\_1\times Q\_2$ on the state sets of the automata, such that for every letter $a\in \Sigma$,

* $q\_1 \to\_a q\_1'$ and $(q\_1',q\_2') \in R$ implies there exists $q\_2$ such that $(q\_1,q\_2) \in R$ and $q\_2 \to\_a q\_2'$, and
* $(q\_1,q\_2) \in R$ and $q\_2\to\_a q\_2'$ implies there exists $q\_1'$ such that $q\_1\to\_a q\_1'$ and $(q\_1',q\_2') \in R$.

More discussion of the universal property of determinization of NFA without $\epsilon$-transitions under different possible scenarios is discussed in this recent paper:

* Thea Li, *Fibrational perspectives on determinization of finite-state automata*, ACT 2024, [arXiv:2410.00675](https://arxiv.org/abs/2410.00675)

The appropriate definition of morphism between $\epsilon$-NFA is not entirely clear to me, though I think one possibility that may work for determinization is to consider forward-and-backward simulations under relations that are downwards-closed under $\epsilon$-transitions on the left and upwards-closed on the right (i.e., if $(q\_1,q\_2) \in R$ and $q\_1' \to\_\epsilon q\_1$ and $q\_2 \to\_\epsilon q\_2'$ then $(q\_1',q\_2') \in R$).

> **Comments:**
> **username_0**: Wow this is very detailed! Thanks!  
> **username_0**: I’m looking at your answer in detail. What’s the relationship between this “forward-and-backward simulation” and standard bisimulation? There is a similarity (!) between the definitions but I can’t see if they are equivalent.  
> **username_1**: they are not equivalent, probably the best way to see it is to define them in terms of [relational composition](https://en.wikipedia.org/wiki/Composition_of_relations). Let $\delta_a^1 \subseteq Q_1\times Q_1$ and $\delta_a^2 \subseteq Q_2\times Q_2$ be the respective transition relations over a letter $a$. A relation $R \subseteq Q_1\times Q_2$ is a forward-and-backward simulation if $\delta_a^1; R = R;\delta_a^2$ for all $a$, and a bisimulation if $\delta_a^1 ; R \subseteq R ; \delta_a^2$ and $\delta_a^1 ; R^\top \subseteq R^\top ; \delta_a^2$ (writing $R^\top$ for the transpose relation).  
> **username_1**: observe that bisimulation is a symmetric relation (if $M_1 \times M_2$ then $M_2 \sim M_1$), but forward-and-backward simulation is not.  
> **username_1**: I kind of screwed up the definition of bisimulation above: it should say $R ; \delta_a^2 \subseteq \delta_a^1 ; R$ and $R^\top ; \delta_a^1 \subseteq \delta_a^2 ; R^\top$.  Concretely that asserts that if $(q_1,q_2) \in R$, then: i) $q_2 \to_a q_2'$ implies there exists $q_1'$ such that $q_1 \to_a q_1'$ and $(q_1',q_2') \in R$, and ii) $q_1 \to_a q_1'$ implies there exists $q_2'$ such that $q_2 \to_a q_2'$ and $(q_1',q_2') \in R$.  
> **username_1**: If you take $R \subseteq Q \times P(Q)$ to be the membership relation, you can check it defines a forward-and-backward simulation between a NFA and its powerset DFA, but not a bisimulation because condition (i) does not hold: it is possible that $q$ is contained in some set of states $X$ such that $X \to_a X'$, but there is no $q' \in X'$ such that $q \to_a q'$.  
> **username_0**: Wow the last comment is nailing exactly what I was trying to do with bisimulations but failed (and so I asked the question). Thanks!  
> **username_1**: yeah, I don't know if the existence of a forward-and-backward simulation but not a bisimulation between a NFA and its determinization is well-known, but it was interesting to me when I learned it from Thea Li.  

---

