# Non-deterministic automata

## Definitions

(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.

###### Definition

A non-deterministic automaton consists of the following data:

• a set of states, $Q$;

• a set, $\Sigma$, of input symbols ;

• a function, $\delta :Q×\Sigma \to 𝒫\left(Q\right)$, called the next state relation,

and

• a predicate, $\mathrm{final}:Q\to \mathrm{bool}=\left\{\perp ,\top \right\}$, the boolean domain.

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 \left(q,\sigma \right)$, of $Q$.

The ‘final’ predicate, of course, returns $\top$ if a state is a final state and $\perp$ 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.)

## Currying $\delta$

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 𝒫\left(Q{\right)}^{\Sigma }$. We thus have for a state, $q\in Q$, $\delta \left(q,\right):\Sigma \to 𝒫\left(Q\right)$. We then also have a product function

$\alpha =\delta ×\left(\mathrm{final}\right):Q\to {Q}^{\Sigma }×\mathrm{bool}.$\alpha = \delta \times (final) : Q \to Q^\Sigma\times bool.

If we now write $\mathrm{HQ}=𝒫\left(Q{\right)}^{\Sigma }×\mathrm{bool}$, we get a functor (for you to check) $H:\mathrm{Set}\to \mathrm{Set}$ and the non-deterministic automaton corresponded precisely to a coalgebra, $\left(Q,\alpha \right)$, for $H$.

## References

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:

• A.Kurz: Coalgebras and Modal Logic. Course Notes for ESSLLI 2001, Version of October 2001. Appeared on the CD-Rom ESSLLI’01, Department of Philosophy, University of Helsinki, Finland, available from site.

Revised on October 24, 2012 09:44:42 by Tim Porter (95.147.236.226)