Mealy and Moore Machines (Finite Automata with Output)

A DFA only says accept or reject at the end. A finite-state transducer produces an output symbol as it reads each input symbol. There are two kinds, named after Edward Moore and George Mealy, and they are exactly the state machines used to design sequential circuits.

Moore machine

A Moore machine is (Q, Σ, Δ, δ, λ, q₀) where Δ is the output alphabet and the output depends only on the current state: λ : Q → Δ.

• For an input of length n it produces n + 1 outputs (one for the start state, then one after each symbol).

State rᵢ outputs i. Reading bit b moves remainder r to (2r + b) mod 3.

Mealy machine

In a Mealy machine the output depends on the state and the input: λ : Q × Σ → Δ, written on each transition as input/output.

• For an input of length n it produces n outputs.
• It usually needs fewer states than an equivalent Moore machine, and reacts in the same step.

Simulating both

mealy = {                              # state: {input: (next state, output)}
    "S0": {"0": ("S0", "0"), "1": ("S1", "0")},
    "S1": {"0": ("S2", "0"), "1": ("S1", "0")},
    "S2": {"0": ("S0", "0"), "1": ("S1", "1")},
}
x = "1101011010"
state, out = "S0", ""
for c in x:
    state, o = mealy[state][c]
    out += o
print("input:       ", x)
print("Mealy output:", out)

r, moore_out = 0, "0"                  # Moore: output the state's remainder
for c in x:
    r = (2 * r + int(c)) % 3
    moore_out += str(r)
print("Moore output:", moore_out)

input:        1101011010
Mealy output: 0001010010
Moore output: 01001222100

The Mealy output has a 1 exactly where 101 has just been completed (positions 3, 5 and 8, counting from 0). The Moore output is one symbol longer.

Converting between them

• Moore → Mealy: put each target state's output on every transition into it. Same number of states.
• Mealy → Moore: split each state by the different outputs on its incoming transitions (state q becomes q/0 and q/1 if both outputs arrive at q). A Mealy machine with n states and m output symbols needs at most n × m Moore states.

Both models are equally powerful (apart from the Moore machine's extra first output).

Mealy, Moore and circuits

In a sequential circuit, flip-flops hold the state. If the outputs are a function of the flip-flops only, it is a Moore circuit (outputs change only at clock edges); if they also depend on the inputs directly, it is a Mealy circuit (outputs can change between clock edges). See Counters and Registers for circuit design.

GATE-style practice questions