# Mealy and Moore Machines — Finite Automata With Output, Sequence Detectors and Converting One Into the Other

Source: https://skills101.in/learn/theory-of-computation/toc-mealy-moore-machines — Skills101 free tutorial (Theory of Computation (TOC)). Updated 2026-11-21.

A [DFA](https://skills101.in/learn/theory-of-computation/dfa-deterministic-finite-automata) 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 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](https://skills101.in/learn-img/theory-of-computation/moore-mod3.svg)

```python
# 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)
```

```text
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](https://skills101.in/learn/theory-of-computation/dfa-deterministic-finite-automata): 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](https://skills101.in/learn-img/theory-of-computation/mealy-01.svg)

```python
# 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)}")
```

```text
0101     -> 0101
1001     -> 0001
0011101  -> 0010001
```

The output has exactly as many symbols as the input. The `1`s 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**.

```python
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))
```

```text
{('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 |

```python
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))
```

```text
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/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 quiz and free certificate: https://skills101.in/learn/theory-of-computation/toc-mealy-moore-machines