Mealy machines

Mealy machines (Hopcroft and Ullman (1979, 42), Salomaa (1973, 31)) are finite-state machines that act as transducers or translators, taking a string on an input alphabet and producing a string of equal length on an output alphabet. Formally, a Mealy machine is a six-tuple

$$M=(Q,\Sigma,\Gamma,\delta,\lambda,q_I)$$ (3.2)

where

• $Q=\{q_1,q_2,\ldots,q_{\vert Q\vert}\}$ is a finite set of states;
• $\Sigma=\{\sigma_1,\sigma_2,\ldots,\sigma_{\vert\Sigma\vert}\}$ is a finite input alphabet;
• $\Gamma=\{\gamma_1,\gamma_2,\ldots,\gamma_{\vert\Gamma\vert}\}$ is a finite output alphabet;
• $\delta:Q\times \Sigma\rightarrow Q$ is the next-state function, such that a machine in state $q_j$, after reading symbol $\sigma_k$, moves to state $\delta(q_j,\sigma_k)\in Q$.
• $\lambda:Q\times \Sigma\rightarrow \Gamma$ is the output function, such that a machine in state $q_j$, after reading symbol $\sigma_k$, writes symbol $\lambda(q_j,\sigma_k)\in\Gamma$; and
• $q_I\in Q$ is the initial state in which the machine is found before the first symbol of a string is processed.

As an example, let $M=(Q,\Sigma,\Gamma,\delta,\lambda,q_I)$ such that:

$Q=\{q_1,q_2\}$, $q_I=q_1$.

$\Sigma=\{{\tt0}, {\tt 1}\}$

$\Gamma=\{{\tt E}, {\tt O}\}$

$\delta(q_1,0)=q_1$, $\delta(q_1,1)=q_2$
$\delta(q_2,0)=q_2$, $\delta(q_2,1)=q_1$

$\lambda(q_1,0)={\tt E}$, $\lambda(q_1,1)={\tt O}$
$\lambda(q_2,0)={\tt O}$, $\lambda(q_2,1)={\tt E}$

This machine, which may also be represented as in figure 2.2, outputs an E if the number of 1s read so far is even and an O if it is odd; for example, the translation of 11100101 is OEOOOEEO.

Figure 2.2: A Mealy machine that outputs an E if the number of 1s read so far is even and an O if it is odd. Transition labels are $\sigma /\gamma$ where $\sigma \in \Sigma$ is the input and $\gamma \in \Gamma$ is the output.