nLab
deterministic automaton

Deterministic automata

Definitions

(For the moment, mostly as an example of a coalgebra for an endofunctor.)

This will give the classical definition as a state-based system and then show how to turn that form into the coalgebraic form. The point is that other coalgebras should then be easier to interpret.

Definition

A deterministic automaton consists of the following data:

  • a set of states, QQ;

  • a set, Σ\Sigma, of inputs ;

  • a function, δ:Q×ΣQ\delta : Q\times \Sigma \to Q, called the next state function,

and

  • a predicate, final:Qbool={,}final : Q \to bool = \{\bot, \top\}, the boolean domain.

In the usual interpretation if the automaton is in state qq, and is ‘given’ the input σ\sigma, then it changes to being in state δ(q,σ)\delta(q,\sigma).

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 in any detail 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 δ:QQ Σ\delta : Q\to Q^\Sigma. We thus have for a state, qQq\in Q, δ(q,):ΣQ\delta(q,) : \Sigma \to Q. We then also have a product function

α=δ×(final):QQ Σ×bool.\alpha = \delta \times (final) : Q \to Q^\Sigma\times bool.

If we now write HQ=Q Σ×boolHQ = Q^\Sigma\times bool, we get a functor (for you to check) H:SetSetH : Set \to Set and the deterministic automaton corresponded precisely to a coalgebra, (Q,α)(Q,\alpha), for HH.

… and the morphisms?

Rather than start with a classically defined morphism of automata, we will take a morphism f:(Q,α)(Q,α)f : (Q,\alpha)\to (Q',\alpha') of coalgebras. We thus have that f:QQf : Q\to Q' is a mapping of states, and that αf=H(f)α\alpha'\circ f = H(f)\circ \alpha. Now let qQq\in Q and σΣ\sigma\in \Sigma, then the equation tells us that δ(f(q),σ)=f(δ(q,σ)\delta'(f(q),\sigma) = f(\delta(q,\sigma) and that the final states of QQ are mapped onto those of QQ'. In other words the concept of morphism of these HH-coalgebras is precisely that of functional simulation of deterministic automata.

Terminal coalgebra

The terminal coalgebra, (T,α T)(T,\alpha_T), for this endofunctor is neat. It has state space, T=𝒫(Σ *)T = \mathcal{P}(\Sigma^*), the power set of the free monoid/ Kleene star of the set of ‘symbol labels’. This power set is precisely the set of all languages over the alphabet Σ\Sigma, as a language is defined to be a subset of Σ *\Sigma^*.

The next state function for (T,α T)(T,\alpha_T) is defined by δ T(L,s)={wΣ *swL}\delta_T(L,s) = \{w\in \Sigma^* |sw \in L\}.

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.

category: computer science

Revised on September 7, 2012 15:49:26 by Tim Porter (95.147.237.101)