Mealy Machine Explained: Worked Output Traces and Moore Conversion
Learn how a Mealy machine places outputs on transitions, then build and trace an overlapping 101 detector. The same example is converted to Moore form and tested for minimality.
KnowledgeGate Team
Exam prep & CS education

The key distinction is local: each Mealy edge consumes an input and emits an output. A three-state detector for 101 makes the timing visible, then the same behaviour can be represented as a four-state Moore machine and checked for minimality.
Mealy machine definition: output belongs to a transition
A Mealy machine is the six-tuple M = (Q, Sigma, Delta, delta, lambda, q0). Here, Q is the finite state set, Sigma is the input alphabet, Delta is the output alphabet, delta: Q x Sigma -> Q is the transition function, lambda: Q x Sigma -> Delta is the output function, and q0 is the start state. The current state and current input jointly determine both the next state and the current output.
On an edge, 1/0 means consume input 1, emit output 0, then enter the destination state. This transition-based output is a basic idea in Theory Of Computation / Automata Theory.
Property | Mealy machine | Moore machine |
|---|---|---|
Output depends on | Current state and input | Current state |
Output label is on | Transition | State |
Output can react when | The input selects an edge | The machine enters or occupies a state |
Build a Mealy sequence detector for overlapping 101
Use Q = {A, B, C}, Sigma = Delta = {0, 1}, and start state A. State A means no useful prefix of 101 is pending. State B means the latest useful suffix is 1. State C means the latest useful suffix is 10.
Current state | Input | Input |
|---|---|---|
|
|
|
|
|
|
|
|
|
The edge C --1/1--> B reports a completed 101 and preserves its final 1 as the prefix of a possible overlapping match. That return to B, rather than A, is what lets the detector find patterns sharing symbols.

Trace input 11010101 and obtain output 00010101
Start in A and process one symbol at a time. Record the output beside the edge that consumes the current input, not beside the state reached afterwards.
Step | Input | Current state | Edge taken | Output | Next state |
|---|---|---|---|---|---|
1 |
|
|
|
|
|
2 |
|
|
|
|
|
3 |
|
|
|
|
|
4 |
|
|
|
|
|
5 |
|
|
|
|
|
6 |
|
|
|
|
|
7 |
|
|
|
|
|
8 |
|
|
|
|
|
Concatenating the emitted bits in step order gives 00010101. The three detected occurrences occupy input positions 2-4, 4-6, and 6-8. They overlap correctly because each match ends in 1, and state B remembers that same 1 as the start of the next possible match.
Two invariants make a quick self-check possible. This machine emits exactly one output symbol per consumed input symbol, so both strings have length 8. Also, output 1 can appear only on C --1/1--> B.

Convert the same Mealy machine to a Moore machine
For each original state, create a Moore-state copy for every distinct output on transitions entering that state. Incoming edges reach A only with output 0 and C only with output 0. They reach B with outputs 0 and 1. We therefore need exactly A0, B0, B1, and C0, whose state outputs are 0, 0, 1, and 0. Start at A0.
Moore state | State output | On | On |
|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Both B0 and B1 inherit the outgoing behaviour of original state B; only their state outputs differ. For input 11010101, the entered states are B0, B0, C0, B1, C0, B1, C0, B1. Their outputs are 00010101, matching the Mealy trace. A Moore start state already has an output before any input is consumed, so align the machines by comparing the output after each consumed symbol. The broader Moore and Mealy Machines: Tracing and Conversion guide focuses on parity and a general A/B conversion; an overlapping 101 detector instead needs an eight-bit trace and a B0/B1 split.
Minimise a Mealy machine by comparing output vectors first
Begin partition refinement with immediate output behaviour. With inputs ordered as (0, 1), the output vectors are:
A = (0, 0)B = (0, 0)C = (0, 1)
The first partition is therefore {A, B} and {C}. Now refine {A, B} by checking destination blocks. On input 0, state A goes to A, which remains in {A, B}, while state B goes to C, which is in {C}. The two states are distinguishable. The final partition is {A}, {B}, {C}, so this three-state Mealy machine is already minimal.
In general, two states are equivalent only if every possible future input string produces the same output string from both. A different immediate output on any input separates them at once. If immediate outputs match, compare the partitions reached by their transitions.
Mealy machine traps: label order, overlap and false final states
Mistake | What goes wrong | Correction |
|---|---|---|
Reading | Input and output are reversed | Read every label as input/output |
Writing outputs on Mealy states | The output dependence becomes unclear | Put outputs on transitions |
Resetting | Overlapping occurrences are missed | Preserve the final |
Shifting the output by one position | Input and output bits no longer align | Emit while taking the current edge |
Marking | A transducer is treated as a language acceptor | Track emitted bits, not accepting states |
During Moore conversion, one copy of B is insufficient because transitions enter it with both outputs 0 and 1. The required split is B0 and B1. The original table also needs exactly six state-input cases, since three states times two input symbols gives 3 x 2 = 6.
Use a 20-second audit: every state has one transition per input symbol, every Mealy edge carries one input and one output, and every consumed bit contributes one emitted bit to the trace.
How exams test Mealy machines
Questions usually move from short tracing tasks to longer construction tasks:
Read the output for a supplied input string.
Fill a missing edge or output in a transition table.
Design a sequence detector from prefix memory.
Convert Mealy to Moore and account for every split state.
Minimise using output partitions and successor refinement.
A reliable attempt order is equally compact. Rewrite each edge as input/output, mark start state A, trace 11010101 to confirm 00010101, then compare the vectors (0,0), (0,0), and (0,1) before refining destinations. The linked GATE guide covers broader state-diagram comparison and minimisation; the overlapping 101 detector provides a focused exercise. Use Moore vs Mealy Machines: GATE Conversion and Minimization for focused conversion and minimisation drills, or follow the wider route through CS Fundamentals for Exams & Placements.
The short version: state memory plus edge output
State remembers the useful past, the current input chooses an edge, and that edge emits the current output. Our three-state 101 detector maps 11010101 to 00010101. Its Moore form needs four states, A0, B0, B1, C0, and minimisation leaves all three Mealy states separate. For a structured next step through the wider Theory of Computation sequence, use GATE Guidance by Sanchit Sir.
Keep learning
Moore and Mealy Machine Conversion: Equivalence, State Splitting and a Worked Trace
Follow a binary 01 detector from a two-state Mealy machine to a split-state Moore machine, prove its output trace, and convert it back cleanly.
Moore and Mealy Machines: Output Tracing, Conversion and Worked Examples
Learn how state outputs and transition outputs change a trace. Two binary examples show parity, Moore-to-Mealy conversion and the exact state splitting needed in the reverse direction.
Moore and Mealy Machines: 7 Tracing and Conversion Mistakes to Avoid
A correct state path can still produce the wrong output string. Use seven checks to fix output timing, conversion labels and state merging, with small binary examples.
Moore vs Mealy Machines for GATE: State Diagrams, Conversion and State Minimization, Solved
Follow one overlapping 11 detector through Mealy and Moore forms, then convert, trace and minimize finite-state machines without losing a clock.





