nLab
Mealy machine

Contents

Contents

Idea

A Mealy machine is a particular type of finite state automaton.

A Mealy machine with input alphabet AA and output alphabet, BB is just a deterministic finite automaton?,which produces a letter of the output alphabet, BB at every transition step. More formally

Definition

A finite Mealy 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;

and

  • λ:Q×AB\lambda:Q\times A \to B, which associates an output symbol with each transition.

Again as for Moore machines, there is an output response function ω A:A *B *\omega_\mathbf{A}:A^*\to B^* defined s follows:

if x=x 1x nA *x= x_1 \ldots x_n\in A^* and the states that A\mathbf{A} passes through when processing this string are q 0,q 1,,q nq_0, q_1, \ldots, q_n, so diagrammatically

q 0x 1q 1x 2x nq n,q_0\xrightarrow{x_1} q_1\xrightarrow{x_2}\ldots \xrightarrow{x_n} q_n,

define ω A(x)=λ(q 0,x 1)λ(q n1,x n)\omega_\mathbf{A}(x)= \lambda(q_0,x_1)\ldots \lambda(q_{n-1},x_n).

Mealy machines and Moore machines have essentially the same descriptive power.

References

Last revised on July 18, 2019 at 09:57:09. See the history of this page for a list of all contributions to it.