duaLab

Automaton

Contents

1. Definition

Fix a finite alphabet $\Sigma$. An automaton is a Sigma-set $(Q,\delta)$ equipped with a subset $F\subseteq Q$ of accepting states: a deterministic automaton without a chosen initial state. A morphism $h:(Q,\delta,F)\to(Q',\delta',F')$ commutes with transitions and satisfies $F=h^{-1}(F')$.

The automaton is orbit-finite if every orbit of its underlying $\Sigma$-set is finite. See Definitions 2.10 and 2.25.

2. Properties

Theorem 2.1 (Topoi of automata)★

Let $\mathcal L$ be the $\Sigma$-set of all languages, and $\mathcal R$ its subobject of regular languages. The category of automata is the slice of the topos of $\Sigma$-sets over $\mathcal L$. The category of orbit-finite automata is the slice of the orbit-finite topos over $\mathcal R$.

Both are Grothendieck topoi. See Theorem 2.12, Corollary 2.13, Proposition 2.26 and Corollary 2.27.

Proposition 2.2 (Language recognition)★

Equip $\mathcal L$ with accepting states the languages containing the empty word. This is the terminal automaton. The unique morphism to it sends each state to the language recognized from that state.

The analogous terminal object for orbit-finite automata is $\mathcal R$. See Corollary 2.15 and Proposition 2.28.

4. References