(For the moment, mostly as an example of a coalgebra for an endofunctor and to start discussion of models for non-determinism.)
This will give the classical definition as a non-deterministic state-based system and then show how to turn that form into the coalgebraic form.
A non-deterministic automaton consists of the following data:
a set of states, $Q$;
a set, $\Sigma$, of input symbols ;
a function, $\delta : Q\times \Sigma \to \mathcal{P}(Q)$, called the next state relation,
and
In the usual interpretation if the automaton is in state $q$, and is ‘given’ the input $\sigma$, then it changes to being in one of the states in the subset, $\delta(q,\sigma)$, of $Q$.
The ‘final’ predicate, of course, returns $\top$ if a state is a final state and $\bot$ otherwise. (There will, in general, be a set of final or ‘accept’ states.)
(For the moment we will not look at the links between automata and languages.)
The first step in transforming this to the coalgebraic form is to curry $\delta$, so as to obtain it in the form $\delta : Q\to \mathcal{P}(Q)^\Sigma$. We thus have for a state, $q\in Q$, $\delta(q,) : \Sigma \to \mathcal{P}(Q)$. We then also have a product function
If we now write $HQ = \mathcal{P}(Q)^\Sigma\times bool$, we get a functor (for you to check) $H : Set \to Set$ and the non-deterministic automaton corresponded precisely to a coalgebra, $(Q,\alpha)$, for $H$.
For a summary of automata theory , look at the Wikipedia.
For a thorough treatment, see
or other texts on the subject.
For the coalgebraic treatment, this is discussed in:
Last revised on October 24, 2012 at 09:44:42. See the history of this page for a list of all contributions to it.