Moore Machine

A Moore machine makes an output String depending only on the state you are in, not on the input you just gave it. Essentially, the Function which produces the next string is executed on the “nodes”, not the “edges”. Unlike Mealy Machines which produce characters on the edges.

Definition 1

A Moore machine is a Finite State Transducer whose output depends only on the current state.

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

• $Q$: finite Set of states
• $\Sigma$: input Alphabet
• $\Delta$: output Alphabet
• $\delta :Q\times \Sigma \to Q$: state transition function
• $\lambda :Q\to \Delta$: output Function (defined only on states)
• $q_0\in Q$: start state

Can always be converted to a Mealy Machine.

Example 1 — Parity Checker

A Moore 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}$

State + Output Table

Each state has a fixed output:

State	Output
$q_{even}$	0
$q_{odd}$	1

Transitions:

• $q_{even}$ on 0 → $q_{even}$
• $q_{even}$ on 1 → $q_{odd}$
• $q_{odd}$ on 0 → $q_{odd}$
• $q_{odd}$ on 1 → $q_{even}$

Example Run

Input: 1011

• Start $q_{even}$ → output 0
• Read 1: go to $q_{odd}$ → output 1
• Read 0: stay in $q_{odd}$ → output 1
• Read 1: go to $q_{even}$ → output 0
• Read 1: go to $q_{odd}$ → output 1

Output string: 01101