AdvancedTheory of Computation (TOC) · Lesson 12 of 14 · Updated ·
Mealy and Moore Machines — Finite Automata With Output, Sequence Detectors and Converting One Into the Other
A DFA reads a whole string and gives one answer at the end: accept or reject. Many real machines need more than that. A vending machine shows a message after every coin. A circuit that watches a serial line must raise a signal the moment a pattern appears. Machines that print an output at every step are called finite-state transducers, and the two standard kinds are the Moore machine and the Mealy machine. Both appear in almost every university TOC and digital-logic syllabus.
1. Two ways to attach output
Both machines are DFAs with no accepting states and an output alphabet Δ (the set of symbols they can print). The only difference is where the output is written.
| Moore machine | Mealy machine | |
|---|---|---|
| Output depends on | the current state only | the current state and the input symbol |
| Output written on | each state (label q/x) | each arrow (label a/x) |
| Output function | λ : Q → Δ | λ : Q × Σ → Δ |
| Outputs for an input of length n | n + 1 (one before any input is read) | n |
| Named after | Edward F. Moore (1956) | George H. Mealy (1955) |
Formally both are 6-tuples (Q, Σ, Δ, δ, λ, q₀): states, input alphabet, output alphabet, transition function, output function and start state. Only the type of λ changes.
The "n + 1 outputs" rule surprises students. A Moore machine is in its start state before it reads anything, and every state has an output, so it prints λ(q₀) first.
2. A Moore machine: remainder modulo 3
Task: read a binary number from left to right and, after every bit, print the remainder of the number read so far when divided by 3.
If the number so far has remainder r and the next bit is b, the new number is 2 × (old number) + b, so the new remainder is (2r + b) mod 3. Three states are enough, one per remainder, and each state simply prints its own remainder.
# Moore machine: remainder of a binary number mod 3
delta = {("r0", "0"): "r0", ("r0", "1"): "r1",
("r1", "0"): "r2", ("r1", "1"): "r0",
("r2", "0"): "r1", ("r2", "1"): "r2"}
out = {"r0": "0", "r1": "1", "r2": "2"}
def moore(delta, out, start, word):
state = start
result = out[state] # a Moore machine prints before reading anything
for ch in word:
state = delta[(state, ch)]
result += out[state]
return result
for w in ["110", "1011", "1111"]:
print(w, "=", int(w, 2), "-> outputs", moore(delta, out, "r0", w), " last:", moore(delta, out, "r0", w)[-1], " check:", int(w, 2) % 3)
110 = 6 -> outputs 0100 last: 0 check: 0
1011 = 11 -> outputs 01222 last: 2 check: 2
1111 = 15 -> outputs 01010 last: 0 check: 0
Read 1011 step by step: start in r0 (print 0); 1 gives 1 (print 1); 10 = 2 (print 2); 101 = 5, remainder 2 (print 2); 1011 = 11, remainder 2 (print 2). Four input bits, five outputs.
Compare this with the divisible-by-3 DFA: the states and arrows are the same. The DFA only asks "is the final state r0?", while the Moore machine reports the state at every step.
3. A Mealy machine: a "01" sequence detector
Task: read a bit stream and print 1 at exactly the moments when the last two bits read are 0 then 1; otherwise print 0. Overlaps count, so in 0101 the pattern ends at positions 2 and 4.
The machine only needs to remember whether the previous bit was 0:
- State A: the last bit was not 0 (or nothing has been read yet).
- State B: the last bit was 0.
From B, reading 1 completes the pattern, so that arrow prints 1. Every other arrow prints 0.
# Mealy machine: print 1 each time the input so far ends in "01"
delta = {("A", "0"): "B", ("A", "1"): "A",
("B", "0"): "B", ("B", "1"): "A"}
out = {("A", "0"): "0", ("A", "1"): "0",
("B", "0"): "0", ("B", "1"): "1"}
def mealy(delta, out, start, word):
state, result = start, ""
for ch in word:
result += out[(state, ch)] # output belongs to the transition
state = delta[(state, ch)]
return result
for w in ["0101", "1001", "0011101"]:
print(f"{w:8} -> {mealy(delta, out, 'A', w)}")
0101 -> 0101
1001 -> 0001
0011101 -> 0010001
The output has exactly as many symbols as the input. The 1s line up with the positions where 01 ends. This is the classic sequence detector question from digital electronics; there the states become flip-flops and the output becomes a logic gate.
4. Converting a Moore machine to a Mealy machine
This direction is easy. On each arrow q → p reading a, print what the Moore machine would print after arriving:
λ′(q, a) = λ(δ(q, a))
The states and arrows stay the same, so the Mealy machine has the same number of states. The only difference: the Mealy machine does not produce the Moore machine's first output λ(q₀). That is why "equivalent" Moore and Mealy machines are compared ignoring the Moore machine's first output.
from itertools import product
def moore(delta, out, start, word):
state = start
result = out[state]
for ch in word:
state = delta[(state, ch)]
result += out[state]
return result
def mealy(delta, out, start, word):
state, result = start, ""
for ch in word:
result += out[(state, ch)]
state = delta[(state, ch)]
return result
# Moore remainder-mod-3 machine
delta = {("r0", "0"): "r0", ("r0", "1"): "r1", ("r1", "0"): "r2",
("r1", "1"): "r0", ("r2", "0"): "r1", ("r2", "1"): "r2"}
out = {"r0": "0", "r1": "1", "r2": "2"}
# Moore -> Mealy: print, on each transition, the output of the state you land in
mealy_out = {(q, a): out[delta[(q, a)]] for (q, a) in delta}
print(mealy_out)
words = ["".join(t) for n in range(1, 11) for t in product("01", repeat=n)]
print("same outputs:", all(moore(delta, out, "r0", w)[1:] == mealy(delta, mealy_out, "r0", w) for w in words))
{('r0', '0'): '0', ('r0', '1'): '1', ('r1', '0'): '2', ('r1', '1'): '0', ('r2', '0'): '1', ('r2', '1'): '2'}
same outputs: True
5. Converting a Mealy machine to a Moore machine
This direction needs more states. In a Mealy machine, two arrows that enter the same state may print different outputs. A Moore state can print only one output, so we split each state into one copy per output that arrives at it: new states are pairs (state, output).
In the detector, arrows enter A with output 0 (from A on 1) and with output 1 (from B on 1). Arrows enter B only with output 0. So A splits into A0 and A1, and B stays as B0:
| Moore state | Prints | On 0 → | On 1 → |
|---|---|---|---|
| A0 (start) | 0 | B0 | A0 |
| A1 | 1 | B0 | A0 |
| B0 | 0 | B0 | A1 |
from itertools import product
def moore(delta, out, start, word):
state = start
result = out[state]
for ch in word:
state = delta[(state, ch)]
result += out[state]
return result
def mealy(delta, out, start, word):
state, result = start, ""
for ch in word:
result += out[(state, ch)]
state = delta[(state, ch)]
return result
# Mealy "ends in 01" detector
delta = {("A", "0"): "B", ("A", "1"): "A", ("B", "0"): "B", ("B", "1"): "A"}
out = {("A", "0"): "0", ("A", "1"): "0", ("B", "0"): "0", ("B", "1"): "1"}
# Mealy -> Moore: split each state by the output printed on the way in
m_delta, m_out = {}, {}
start = ("A", "0") # the start state gets any output; Moore's first output is ignored
todo, seen = [start], {start}
while todo:
q, o = todo.pop()
m_out[(q, o)] = o
for a in "01":
nxt = (delta[(q, a)], out[(q, a)])
m_delta[((q, o), a)] = nxt
if nxt not in seen:
seen.add(nxt)
todo.append(nxt)
for st in sorted(m_out):
print(st[0] + st[1], "output", m_out[st], " on 0 ->", "".join(m_delta[(st, "0")]), " on 1 ->", "".join(m_delta[(st, "1")]))
words = ["".join(t) for n in range(1, 11) for t in product("01", repeat=n)]
print("same outputs on", len(words), "strings:",
all(moore(m_delta, m_out, start, w)[1:] == mealy(delta, out, "A", w) for w in words))
A0 output 0 on 0 -> B0 on 1 -> A0
A1 output 1 on 0 -> B0 on 1 -> A0
B0 output 0 on 0 -> B0 on 1 -> A1
same outputs on 2046 strings: True
The 2-state Mealy machine became a 3-state Moore machine. In general, a Mealy machine with n states and k possible outputs gives a Moore machine with at most n × k states (plus possibly one extra start state if the original start state has incoming arrows with an output you do not want to print first).
6. Which one to use?
| Question | Moore | Mealy |
|---|---|---|
| Fewer states for the same job? | usually more | usually fewer |
| When does output change? | one step later, after entering a state | immediately, on the input itself |
| Output stable between clock ticks (hardware)? | yes, depends on state only | can change if the input changes mid-cycle |
| Same computing power? | yes | yes |
Both recognise exactly the same input–output behaviours (up to the first Moore output). Neither is more powerful than a DFA in terms of the languages behind them; they only report more.
Common mistakes
- Writing n outputs for a Moore machine. It prints λ(q₀) first, so an input of length n gives n + 1 outputs.
- Putting outputs on arrows in a Moore diagram, or on states in a Mealy diagram. Moore:
q/xinside the state. Mealy:a/xon the arrow. - In Mealy → Moore, splitting a state into a copy for every output symbol even when that output never enters it. Only create copies for outputs that actually arrive.
- Forgetting that Moore → Mealy keeps the same states. No new states are needed.
- Treating the machines as acceptors. They have no final states; their answer is the output string.
Quick recap
- Moore: output on states, λ : Q → Δ, n + 1 outputs. Mealy: output on transitions, λ : Q × Σ → Δ, n outputs.
- Remainder mod 3 is a natural Moore machine: state = remainder, print the state.
- A "01" sequence detector is a natural 2-state Mealy machine: the arrow B --1/1--> A prints the 1.
- Moore → Mealy: λ′(q, a) = λ(δ(q, a)), same states.
- Mealy → Moore: split states by incoming output, at most n × k states.
- Both models are equally powerful; always check equivalence by simulating many strings.