nLab Moore machine




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


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

  • QQ, a finite set of states;

  • AA, an input alphabet;

  • BB, an output alphabet;

  • q 0q_0, an initial state;

  • δ:Q×AQ\delta: Q\times A\to Q, a transition function;


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

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

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


Last revised on August 25, 2023 at 11:54:46. See the history of this page for a list of all contributions to it.