An Introduction to Formal Languages and Automata, 7th Edition

A.2 MEALY MACHINES

In a Mealy machine, the output produced by each transition depends on the internal state prior to the transition and the input symbol used in the transition, so we can think of the output produced during the transition.

DEFINITION A.1

A Mealy machine is defined by the sextuple

$$M=(Q,\Sigma ,\Gamma ,\delta ,\theta ,q_0),$$

where

1. Q is a finite set of internal states,
2. Σ is the input alphabet,
3. Γ is the output alphabet,
4. δ: Q × Σ → Q is the transition function,
5. θ: Q × Σ →Γ is the output function,
6. q₀ ∈ Q is the initial state of M.

The machine starts in state q₀ at which time all input is available for processing. If at time t_n the Mealy machine is in state q_i, the current input symbol is a, and δ(q_i, a) = q_j, θ(q_i, a) = b, the machine will enter state