Skills101

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 machineMealy machine
Output depends onthe current state onlythe current state and the input symbol
Output written oneach state (label q/x)each arrow (label a/x)
Output functionλ : Q → Δλ : Q × Σ → Δ
Outputs for an input of length nn + 1 (one before any input is read)n
Named afterEdward 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 with states r0/0, r1/1 and r2/2: r0 loops on 0 and goes to r1 on 1, r1 goes to r2 on 0 and back to r0 on 1, r2 goes to r1 on 0 and loops on 1; input 1011 gives outputs 0 1 2 2 2

# 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 with two states A and B: A loops on 1/0 and goes to B on 0/0, B loops on 0/0 and goes back to A on 1/1, which is the only arrow that prints 1; input 0011101 gives output 0010001

# 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 statePrintsOn 0 →On 1 →
A0 (start)0B0A0
A11B0A0
B00B0A1
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?

QuestionMooreMealy
Fewer states for the same job?usually moreusually fewer
When does output change?one step later, after entering a stateimmediately, on the input itself
Output stable between clock ticks (hardware)?yes, depends on state onlycan change if the input changes mid-cycle
Same computing power?yesyes

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/x inside the state. Mealy: a/x on 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.

Practice what you learned

📝 Quiz: Mealy and Moore Machines5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →