# nLab nondeterministic automaton

Non-deterministic automata

### Context

#### Computing

intuitionistic mathematics

# 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\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.)

## Properties

### Coalgebraic description

The first step in transforming the above definition 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

$\alpha = \delta \times (final) : Q \to \mathcal{P}(Q)^\Sigma\times bool.$

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

Monographs: