Every automaton so far has given a one-word answer at the end of the input: accept or reject. But many real machines must respond while they run. A traffic light shows a colour in every state. A serial-line receiver raises a flag the moment a certain bit pattern arrives. A vending machine releases a product when enough coins are in.
Finite automata that produce an output string instead of a yes/no answer are called finite-state transducers, or finite automata with output. The two classic kinds are named after Edward F. Moore and George H. Mealy, who introduced them in the 1950s for designing sequential circuits.
A Moore machine produces an output that depends only on the current state. A Mealy machine produces an output that depends on the current state and the current input symbol, i.e. on the transition taken.
In this chapter we will define both machines, design several of them (remainder calculator, sequence detector, 2's complement), convert between them, and compare them. Every machine here was simulated by a program, its outputs were checked for all inputs up to length 10–12, and each conversion was checked to produce the same output as the original on all those inputs.
Moore Machine
A Moore machine is a 6-tuple:
M = (Q, Σ, Δ, δ, λ, q0)
Q finite set of states
Σ input alphabet
Δ output alphabet
δ transition function δ : Q × Σ → Q
λ output function λ : Q → Δ (one output per state)
q0 start stateThere are no final states. The "result" is the output string.
The machine emits λ(q0) as soon as it starts, then after each input symbol it moves to a new state and emits that state's output. So on an input a1a2…an passing through states q0, q1, …, qn, the output is:
λ(q0) λ(q1) λ(q2) … λ(qn) ← n + 1 symbols for n input symbolsIn particular, a Moore machine produces one output symbol even for the empty input: λ(q0).
In diagrams, a Moore state is written with its output: q1/1 means state q1 with output 1.
Example 1: Remainder of a binary number mod 3
Read a binary number from the most significant bit. After each bit, output the remainder (0, 1 or 2) of the number read so far when divided by 3.
Key idea. If the number read so far has value v and we read bit b, the new value is 2v + b. So the new remainder is (2r + b) mod 3, where r is the old remainder. We only need to remember r, so three states suffice: qr = "remainder r".
State | 0 | 1 | Output λ |
|---|---|---|---|
→ q0 | q0 | q1 | 0 |
q1 | q2 | q0 | 1 |
q2 | q1 | q2 | 2 |
(From q1 on 0: (2·1 + 0) mod 3 = 2. From q2 on 0: (2·2 + 0) mod 3 = 1. From q2 on 1: (2·2 + 1) mod 3 = 2.)
──► q0/0 ──1──► q1/1 ──0──► q2/2
⟲ 0 ⟲ 1
remaining arrows: q1 ──1──► q0 q2 ──0──► q1Trace on input 1010 (decimal 10):
Prefix read | Value | State | Output |
|---|---|---|---|
ε | 0 | q0 | 0 |
1 | 1 | q1 | 1 |
10 | 2 | q2 | 2 |
101 | 5 | q2 | 2 |
1010 | 10 | q1 | 1 |
Output: 01221 (5 symbols for 4 input symbols). The last symbol, 1, is indeed 10 mod 3.
Notice that a DFA is really a special Moore machine: give every state the output 1 if it is final and 0 otherwise, and the last output symbol tells you accept or reject. Our remainder machine with "accept iff output is 0" is exactly the DFA for binary numbers divisible by 3.
Mealy Machine
A Mealy machine is also a 6-tuple, but its output is attached to transitions:
M = (Q, Σ, Δ, δ, λ, q0)
δ : Q × Σ → Q
λ : Q × Σ → Δ (one output per transition)For each input symbol, the machine emits λ(q, a) and moves to δ(q, a). So the output for a1…an is:
λ(q0, a1) λ(q1, a2) … λ(q(n-1), an) ← exactly n symbolsFor the empty input, a Mealy machine outputs nothing (ε). Arrows are labelled input/output, e.g. 1/0 means "on input 1, output 0".
Example 2: Overlapping sequence detector for 101
Output 1 at the moment the last three input bits are 101, otherwise 0. Overlaps count: in 10101 the pattern ends at positions 3 and 5.
States remember how much of 101 we have matched so far:
A: nothing useful matched yet;
B: the input ends with 1;
C: the input ends with 10.
State | On 0 (next, output) | On 1 (next, output) |
|---|---|---|
→ A | A, 0 | B, 0 |
B | C, 0 | B, 0 |
C | A, 0 | B, 1 |
──► A ──1/0──► B ──0/0──► C
⟲ 0/0 ⟲ 1/0
C ──1/1──► B (pattern complete; the final 1 can start the next 101)
C ──0/0──► A (100 kills the match)Why does C go to B on 1 and not back to A? After 101, the last symbol is 1, which is the first symbol of a possible next 101. That is what makes the detector overlapping. (A non-overlapping detector would go to A instead.)
Trace on 0101101:
input : 0 1 0 1 1 0 1
state : A ─► A ─► B ─► C ─► B ─► B ─► C ─► B
output: 0 0 0 1 0 0 1Output 0001001: the pattern 101 ends at positions 4 and 7.
Example 3: 2's complement (bits fed LSB first)
The 2's complement of a binary number can be formed by this rule: scanning from the least significant bit, copy every bit up to and including the first 1, then invert all remaining bits. That is a two-state Mealy machine:
State | On 0 (next, output) | On 1 (next, output) |
|---|---|---|
→ N ("no 1 seen yet") | N, 0 | Y, 1 |
Y ("first 1 seen") | Y, 1 | Y, 0 |
Take the 8-bit number 01101000 (decimal 104). Fed LSB first, the input is 0,0,0,1,0,1,1,0:
input (LSB first): 0 0 0 1 0 1 1 0
state : N ─► N ─► N ─► N ─► Y ─► Y ─► Y ─► Y ─► Y
output : 0 0 0 1 1 0 0 1Reading the output backwards (MSB first) gives 10011000 = 152 = 256 − 104. Correct. Note that this only works LSB first: the machine must see the low bits first to know when the first 1 appears.
Equivalence of Moore and Mealy Machines
A Moore machine always produces one extra symbol at the start (λ(q0)), so their outputs can never be literally equal. The standard definition ignores that first symbol:
A Moore machine M1 and a Mealy machine M2 are equivalent if, for every input string w, the output of M1 on w with its first symbol removed equals the output of M2 on w.
With this definition, every Moore machine has an equivalent Mealy machine and vice versa.
Converting Moore to Mealy
This direction is easy and never needs new states. A Moore machine outputs λ(p) when it enters p. So a Mealy machine can produce the same symbol on the arrow that enters p:
Mealy output λ'(q, a) = λ( δ(q, a) ) (same states, same δ)Applying it to the remainder machine of Example 1:
State | On 0 (next, output) | On 1 (next, output) |
|---|---|---|
→ q0 | q0, 0 | q1, 1 |
q1 | q2, 2 | q0, 0 |
q2 | q1, 1 | q2, 2 |
On input 1010 this Mealy machine outputs 1221, which is the Moore output 01221 without its first symbol. A Moore machine with n states gives a Mealy machine with the same n states.
Converting Mealy to Moore
The other direction can need more states. The problem: in a Mealy machine, different arrows entering the same state may carry different outputs, but a Moore state can only have one output. The fix is to split such a state into one copy per output.
1. For each state q, list the outputs on all arrows entering q.
2. If q is entered with only one output o, keep q as one Moore state with λ = o.
If q is entered with outputs o1, o2, …, create copies q_o1, q_o2, … (λ(q_o) = o).
If q is entered by no arrow (e.g. only the start), keep one copy with any output.
3. Each copy of q gets q's outgoing arrows: on input a, go to the copy of
δ(q, a) whose output is the Mealy output λ(q, a).
4. The start state is a copy of q0 (the first output is ignored anyway).With n Mealy states and m output symbols, the Moore machine has at most m · n states (some books add one extra start state, giving m · n + 1).
Example 4: The 101 detector as a Moore machine
Entering arrows in the Mealy machine of Example 2:
A is entered by A –0/0 and C –0/0: only output 0. Keep A (output 0).
B is entered by A –1/0, B –1/0 and C –1/1: outputs 0 and 1. Split into B0 and B1.
C is entered by B –0/0 only. Keep C (output 0).
Moore state | 0 | 1 | Output |
|---|---|---|---|
→ A | A | B0 | 0 |
B0 | C | B0 | 0 |
B1 | C | B0 | 1 |
C | A | B1 | 0 |
4 states instead of 3. B1 means "just completed 101", and it is the only state with output 1. Trace on 0101101: states A, A, B0, C, B1, B0, C, B1; output 00001001, i.e. 0 followed by the Mealy output 0001001.
The extra state is not an accident: a Moore machine's output is "one step late" in the sense that it can only show the result after entering a state, so it needs a separate state to represent "pattern just completed".
Example 5: An exam-style table
Mealy machine, Σ = Δ = {0, 1}, start q1:
State | On 0 (next, output) | On 1 (next, output) |
|---|---|---|
→ q1 | q3, 0 | q2, 0 |
q2 | q1, 1 | q4, 0 |
q3 | q2, 1 | q1, 1 |
q4 | q4, 1 | q3, 0 |
Step 1: outputs entering each state.
q1 ← (q2, 0)/1, (q3, 1)/1 outputs {1} → q1 (output 1)
q2 ← (q1, 1)/0, (q3, 0)/1 outputs {0, 1} → q20, q21
q3 ← (q1, 0)/0, (q4, 1)/0 outputs {0} → q3 (output 0)
q4 ← (q2, 1)/0, (q4, 0)/1 outputs {0, 1} → q40, q41Step 2: build the table. Each copy inherits the outgoing arrows of the original, pointing to the copy that matches the Mealy output:
Moore state | 0 | 1 | Output |
|---|---|---|---|
→ q1 | q3 | q20 | 1 |
q20 | q1 | q40 | 0 |
q21 | q1 | q40 | 1 |
q3 | q21 | q1 | 0 |
q40 | q41 | q3 | 0 |
q41 | q41 | q3 | 1 |
For example, q3 on 0 goes to q2 with output 1 in the Mealy machine, so in the Moore machine q3 on 0 goes to q21.
Check on input 0110. Mealy: q1 –0/0→ q3 –1/1→ q1 –1/0→ q2 –0/1→ q1, output 0101. Moore: q1(1) → q3(0) → q1(1) → q20(0) → q1(1), output 10101. Dropping the first symbol gives 0101. ✓
The start state q1 has output 1 here simply because arrows entering it carry output 1. That first symbol is ignored in the equivalence. Some textbooks prefer to add a fresh start state with a neutral output and q1's outgoing arrows; both answers are accepted.
Moore vs Mealy
Feature | Moore machine | Mealy machine |
|---|---|---|
Output function | λ : Q → Δ | λ : Q × Σ → Δ |
Output depends on | Current state only | Current state and current input |
Output written on | States (q/o) | Transitions (a/o) |
Output length for input of length n | n + 1 | n |
Output on empty input | λ(q0) | ε |
Number of states for the same behaviour | Same or more | Same or fewer |
Reaction to input (in hardware) | Output changes only after the state changes (on a clock edge); stable and glitch-free | Output can change as soon as the input changes; reacts one cycle earlier but may glitch |
Conversion | To Mealy: same states | To Moore: up to m · n states |
Power | Equivalent (ignoring Moore's initial output) | |
In digital design, sequential circuits are built as either kind: a Moore circuit's outputs come only from flip-flops (state), while a Mealy circuit's outputs are a combinational function of flip-flops and current inputs. That is the hardware meaning of the λ : Q → Δ vs λ : Q × Σ → Δ difference.
Common Mistakes
Forgetting Moore's initial output. A Moore machine on n inputs gives n + 1 outputs, starting with λ(q0).
Giving a Moore machine final states. Transducers have no final states; the output string is the answer.
Using the source state's output in Moore → Mealy. The Mealy output on q –a→ p is λ(p), the output of the state being entered.
Splitting by outgoing outputs in Mealy → Moore. Split by the outputs on arrows entering a state.
Pointing a copy's arrow to the wrong copy. The target copy is chosen by the Mealy output of that arrow.
Non-overlapping vs overlapping detectors. Read the question carefully: after a complete match, overlapping detectors keep the useful suffix; non-overlapping ones restart.
Expecting identical outputs. Moore and Mealy outputs are compared after dropping Moore's first symbol.
Practice and GATE-Style Questions
Q1. A Moore machine is given an input of length 10. How many output symbols does it produce? A Mealy machine?
Moore: 11. Mealy: 10.
Q2. Design a Mealy machine that outputs the 1's complement of its binary input.
One state q with two self-loops: 0/1 and 1/0. A Moore machine needs 2 states, because each output value must belong to its own state: S0/0 and S1/1, where both states go to S1 on input 0 and to S0 on input 1. Either state can be the start state, since the first Moore output is ignored.
Q3. Using the remainder-mod-3 Moore machine, what is the output on 111?
Prefix values 0, 1, 3, 7 give remainders 0, 1, 0, 1. Output 0101.
Q4. What is the minimum number of states of a Mealy machine and of a Moore machine for the overlapping 101 detector?
Mealy: 3 (A, B, C in this chapter). Moore: 4, because "just saw 101" must be a separate state with output 1.
Q5. A Mealy machine has 5 states and its output alphabet has 3 symbols. What is the maximum number of states in the equivalent Moore machine obtained by state splitting?
5 × 3 = 15 (each state split into at most one copy per output symbol). If the book adds a separate start state, 16.
Q6. Interview: in a hardware FSM, why might you prefer a Moore machine even though it needs more states?
Moore outputs depend only on the registered state, so they change only on clock edges and do not glitch when inputs change mid-cycle. That makes timing analysis simpler and outputs safer to feed into other logic. Mealy machines react in the same cycle and often need fewer states, so they are chosen when latency or area matters more.
Summary
Moore and Mealy machines are finite automata that produce output instead of accepting or rejecting; they have no final states.
Moore: λ : Q → Δ; output on states; n + 1 outputs for n inputs, starting with λ(q0).
Mealy: λ : Q × Σ → Δ; output on transitions; n outputs for n inputs.
Moore → Mealy: λ'(q, a) = λ(δ(q, a)); same states.
Mealy → Moore: split each state by the outputs on arrows entering it; at most m · n states.
They are equivalent once Moore's first output is ignored.
A DFA is a Moore machine whose output says "final" or "not final".
Moore talks in states, Mealy talks on arrows. Moore is one symbol longer, Mealy is often one state smaller.