Contents

Contents

Idea

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

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

Definition

A finite Mealy 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\times A \to B$, which associates an output symbol with each transition.

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

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

$q_0\xrightarrow{x_1} q_1\xrightarrow{x_2}\ldots \xrightarrow{x_n} q_n,$

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