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.
KnowledgeGate Team
Exam prep & CS education

Your state path looks correct, but your output string disagrees with the answer. Separate three things: where the output is attached, when you record it, and how conversion changes state labels. These seven checks use small binary examples to make each distinction clear.
1. Reading a Moore output as an edge output
Binary labels look alike, so it is easy to read every 1 as an output. In a Moore machine, output is lambda(q), determined by the state. In a Mealy machine, output is lambda(q, x), determined by the state and current input. In both, delta(q, x) gives the next state.
Use this Moore machine, initially at A:
State/output | Next on 0 | Next on 1 |
|---|---|---|
A/0 | A | B |
B/1 | B | A |
On input 1, B goes to A. Writing output 1 from the edge label is wrong: the post-transition output is A's 0.
Label states A/0, B/1 and Moore edges with inputs alone. The broad theory and parity example are in Moore and Mealy tracing and conversion; the Mealy machine explainer works through sequence detection and overlap. Read this A/B table as the diagnostic for the edge-versus-state mistake.
2. Dropping or double-counting the initial Moore output

Assuming output length always equals input length hides the initial observation. Here, include the Moore output at t=0, then record the reached state's output after each input.
For input 1011, trace one symbol per column:
Time | t=0 | t=1 | t=2 | t=3 | t=4 |
|---|---|---|---|---|---|
Input | 1 | 0 | 1 | 1 | |
State | A | B | B | A | B |
Output | 0 | 1 | 1 | 0 | 1 |
The full output is 01101; the post-input output is 1101. Dropping the initial symbol from a full trace loses an observation; adding it twice gives the incorrect 001101.

Mark t=0 separately. Four inputs give 4+1=5 observations with it, or four without it. Neither convention is universal: follow the question. Ordinary Mealy tracing records one output per consumed input.
3. Copying the source output during Moore-to-Mealy conversion
The source output sits near the outgoing arrow, tempting you to copy it. For post-transition alignment, copy the destination output:
lambda_M(q, x) = lambda_Moore(delta(q, x)).
The complete converted table is:
Source | Input | Destination | Edge output |
|---|---|---|---|
A | 0 | A | 0 |
A | 1 | B | 1 |
B | 0 | B | 1 |
B | 1 | A | 0 |
From A, input 1011 traverses A -> B -> B -> A -> B. Destination outputs give 1101; copying source outputs gives 0110, a different alignment.
Follow the arrow first, then copy the output. Compare with the Moore string after removing its initial 0. An ordinary Mealy machine cannot emit that initial symbol before reading input.
4. Keeping one Moore state for conflicting incoming outputs
Preserving the original state count feels natural, but can make conversion impossible. Consider a separate Mealy echo machine: initial X has self-loops 0/0 and 1/1. One Moore state X cannot have both fixed outputs.
Split it into X0/output 0 and X1/output 1:
State/output | Next on 0 | Next on 1 |
|---|---|---|
X0/0 | X0 | X1 |
X1/1 | X0 | X1 |
Choose initial X0. Input 101 follows X0 -> X1 -> X0 -> X1, giving full Moore output 0101. Its post-input suffix 101 matches the Mealy output.
Split each destination by distinct incoming outputs, then route transitions to the matching copy. Extra initial-state handling depends on the required initial output. Conversion neither always doubles the state count nor always adds exactly one state.
5. Merging states just because their current outputs match
Equal outputs suggest equivalence, but future behaviour also matters. Use this separate Moore machine, initially at C:
State/output | Next on 0 | Next on 1 |
|---|---|---|
C/0 | C | E |
D/0 | C | C |
E/1 | D | E |
All states are reachable: input 1 reaches E; 10 reaches D. The initial output partition is {C,D}, {E}.
Merging C and D because both output 0 is wrong. Input 1 takes C to E/output 1, but D to C/output 0. Their full traces are 01 and 00, respectively.
Refine to {C}, {D}, {E}. Equal current outputs are necessary; compare successor blocks for every input until refinement stabilises. For Mealy minimisation, also compare per-input output vectors.
6. Testing a conversion on only one convenient input
A passing trace feels like proof. In the A/B machine, input 0 produces 0 whether you copy source or destination outputs. Input 1 exposes the error: correct output 1, incorrect output 0.
Use these checks from initial A:
Input | Correct Mealy output | Checks |
|---|---|---|
Empty | Empty | Initial-output convention |
|
| A self-loop |
|
| A -> B |
|
| B self-loop |
|
| B -> A |
Cover transitions and compare aligned outputs. These traces detect the demonstrated errors; they are not a general equivalence proof. Apply the same checks to Mealy machine practice questions. For a full equivalence proof, compare the conversion rules in Moore and Mealy machine conversion; that earlier post owns proof of equivalence, while this one isolates the counterexamples that expose tracing mistakes.
7. Confusing output bits with acceptance, then skipping the final audit
DFA exercises train you to look for accepting states. That makes "output 1 means accepted" tempting, but incorrect here. From A, input 1 reaches B and emits 1 because B's output is 1. No accepting-state set has been supplied.
Run a trace in a fixed order. First write the machine type and initial state. For Moore, record the current state output before consuming the first symbol when the convention includes t=0; then consume one symbol, move, and record the destination output. For Mealy, consume the symbol, record the edge output, and move. During conversion, annotate every destination output before filling the edge labels. During minimisation, partition by current output, refine with successor blocks, and compare each Mealy output vector. A final row-by-row check with one transition from every state catches a copied label that a single convenient input can hide.
Before submitting, check machine type, initial state, input/output label positions, observation convention and complete transition rows. This is the final audit to carry into broader revision through Theory of Computation / Automata Theory. If you need guided practice, continue with the Theory of Computation course.
Keep learning
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 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.
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.
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.





