Mealy and Moore Machines

Automata that talk back

A DFA only answers yes or no at the end: accept or reject. Many real machines must respond while they read. A vending machine gives change, a traffic light switches colour, and a circuit raises an alarm when it sees a pattern. Mealy and Moore machines are finite automata with an output tape. They are also called finite-state transducers. They have no accepting states: their whole job is the output string.

Both are made of states Q, an input alphabet Σ, an output alphabet Δ, a transition function δ, a start state q₀ and an output function λ. The only difference is what λ looks at.

Mealy: output on the arrows

λ(q, a) depends on the state and the input. Each arrow is labelled input/output: 1/0 means “on reading 1, write 0 and move”. Reading n symbols gives n outputs.

Moore: output in the states

λ(q) depends on the state only. Each state is labelled state/output. The output is written whenever the machine is in a state, including the start state before any input, so n symbols give n + 1 outputs.

Example: a 101 detector, both ways

Output 1 every time the input ends with 101 (overlaps count).

Mealy (3 states):

State	on 0	on 1
S0 (nothing useful yet)	S0, write 0	S1, write 0
S1 (just saw 1)	S2, write 0	S1, write 0
S2 (just saw 10)	S0, write 0	S1, write 1

Moore (4 states, the extra one remembers “just saw 101”):

State	on 0	on 1	Output
S0	S0	S1	0
S1	S2	S1	0
S2	S0	S3	0
S3	S2	S1	1

On the input 10101101:

	Output
Mealy	00101001 (8 symbols)
Moore	0 + 00101001 = 000101001 (9 symbols)

Apart from the first symbol, the outputs are the same. The Moore machine needs one more state because “I just finished a 101” has to become a state of its own.

Mealy vs Moore

	Mealy	Moore
Output depends on	state and input	state only
Written on	transitions	states
Outputs for n inputs	n	n + 1
States needed	usually fewer	often more
In a circuit	output can change as soon as the input changes	output changes only when the state changes (on the clock), so it is steadier

Converting between them

Moore → Mealy keeps the same states. For every arrow p → q on symbol a, write the output of q on the arrow: a/λ(q). Afterwards some states may have become identical and can be merged. In the 101 detector, S1 and S3 merge, giving back the 3-state Mealy machine.

Mealy → Moore splits states:

1. For each state q, collect the outputs on the arrows that enter q.
2. If they are all the same output o, rename q to q/o. If there are several, make one copy q/o for each.
3. Every copy keeps q’s outgoing arrows. An arrow that wrote o while entering r now goes to r/o.

In the 101 detector, S1 is entered with output 0 (from S0 and S1) and with output 1 (from S2), so it splits into S1/0 and S1/1. S1/1 is exactly the Moore machine’s S3. Press Convert in the model to watch this happen.

Two more examples in the model

• Two’s complement (Mealy). Read the bits from the right. Copy every bit up to and including the first 1, then flip all the rest. State A means “no 1 yet” and B means “flipping”. 01101100 (108) becomes 10010100, which is −108 in two’s complement.
• Remainder mod 3 (Moore). Each state is a remainder (0, 1 or 2) and outputs it. Reading bit b turns remainder r into (2r + b) mod 3, so after 1101 (13) the last output is 1.

Code

# Mealy: delta[state][symbol] = (next state, output)
mealy = {'S0': {'0': ('S0', '0'), '1': ('S1', '0')},
         'S1': {'0': ('S2', '0'), '1': ('S1', '0')},
         'S2': {'0': ('S0', '0'), '1': ('S1', '1')}}

# Moore: delta[state][symbol] = next state, out[state] = output
moore = {'S0': {'0': 'S0', '1': 'S1'}, 'S1': {'0': 'S2', '1': 'S1'},
         'S2': {'0': 'S0', '1': 'S3'}, 'S3': {'0': 'S2', '1': 'S1'}}
out = {'S0': '0', 'S1': '0', 'S2': '0', 'S3': '1'}

def run_mealy(delta, q, s):
    result = ''
    for c in s:
        q, o = delta[q][c]
        result += o                    # output comes with the transition
    return result

def run_moore(delta, out, q, s):
    result = out[q]                    # the start state outputs first
    for c in s:
        q = delta[q][c]
        result += out[q]               # output comes from the new state
    return result

def mealy_to_moore(delta):
    """Split each state by the outputs written on the arrows that enter it."""
    incoming = {q: set() for q in delta}
    for p in delta:
        for q, o in delta[p].values():
            incoming[q].add(o)
    new_delta, new_out = {}, {}
    for q in delta:
        for o in sorted(incoming[q]) or ['0']:
            name = f'{q}/{o}'
            new_out[name] = o
            new_delta[name] = {c: f'{r}/{o2}' for c, (r, o2) in delta[q].items()}
    return new_delta, new_out

print(run_mealy(mealy, 'S0', '10101101'))          # 00101001
print(run_moore(moore, out, 'S0', '10101101'))     # 000101001  (one more output)
d, o = mealy_to_moore(mealy)
print(sorted(d))                                   # ['S0/0', 'S1/0', 'S1/1', 'S2/0']
print(run_moore(d, o, 'S0/0', '10101101'))         # 000101001

Common mistakes

• Forgetting the Moore start output. A Moore machine writes n + 1 symbols for n inputs.
• Looking for accepting states. Transducers don’t accept or reject. Only the output matters.
• Splitting by outgoing outputs. In Mealy → Moore, a state is split by the outputs on the arrows that enter it.
• Expecting the same number of states. Mealy → Moore can multiply the states by the size of the output alphabet.