Mealy Machine

A Mealy machine makes an output String depending on the state and the input you just gave it. Essentially, the Function which produces the next string is executed on the “edges” or “arrows”, not the “nodes”. Unlike a Moore Machine which produces characters on the nodes.

Definition 1

A Mealy machine is a Finite State Transducer whose output depends on both the current state and the current input.

Formally a 6-Tuple ($Q,\sum ,\Delta ,\delta ,\lambda ,q_0$):

• $Q$: finite Set of states
• $\sum$: input Alphabet
• $\Delta$: output Alphabet
• $\delta :Q\times \sum \to Q$: state transition function
• $\lambda :Q\times \sum \to \Delta$: output Function
• $q_0\in Q$: start state

Can always be converted to a Moore Machine.

Example 1 — Parity Checker

A Mealy machine that outputs 1 whenever the number of 1s seen so far is odd, otherwise 0.

Components

• $Q=\{q_{even},q_{odd}\}$
• $\Sigma =\{0,1\}$
• $\Delta =\{0,1\}$
• $q_0=q_{even}$

Transition + Output Table

Each entry = (next state, output):

Current State	Input = 0	Input = 1
$q_{even}$	($q_{even},0$)	($q_{odd},1$)
$q_{odd}$	($q_{odd},1$)	($q_{even},0$)

Example Run

Input: 1011

• Start $q_{even}$
• Read 1: → ($q_{odd}$, output 1)
• Read 0: → ($q_{odd}$, output 1)
• Read 1: → ($q_{even}$, output 0)
• Read 1: → ($q_{odd}$, output 1)

Output string: 1101