nLab Moore machine

Idea

Moore machines are a special type of finite state automata and in particular a special case of Mealy machines (see there for more).

Definition

A finite Moore machine, $\mathbf{A}$, consists of

• $Q$, a finite set of states;

• $A$, an input alphabet;

• $B$, an output alphabet;

• $q_0$, an initial state;

• $\delta: Q\times A\to Q$, a transition function;

and

• $\lambda:Q\to B$, the state output function.

These determine an output response function, $\omega_\mathbf{A}:A^*\to B^*$ and a characteristic function $\chi_\mathbf{A}:A^*\to B$ that picks out the language recognised by the machine.

Here we have, as usual, denoted by $A^*$ the free monoid (of all strings of symbols) over the ‘alphabet’ $A$, etc.

Related entries

• Mealy machine

• automaton

References

• Mark V. Lawson, Finite automata, CRC Press, see also here for a shorter version in the form of Course Notes.

• Guido Boccali, Bojana Femić, Andrea Laretto, Fosco Loregian, Stefano Luneia, The semibicategory of Moore automata (arXiv:2305.00272)