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

An 01 detector makes the conversion issue concrete: split a destination state when incoming outputs differ, trace both machines, and then reverse the conversion. The result is a reliable way to test equivalence even when diagrams and state counts differ.
Moore and Mealy equivalence starts with where the output lives
Both models use states Q, input alphabet Sigma, output alphabet Delta, transition function delta, and initial state q0. A Moore output function lambda: Q -> Delta labels states. A Mealy function lambda: Q x Sigma -> Delta labels transitions.
This location changes the trace. A Mealy output accompanies the transition for the current input. A Moore output belongs to the state reached, while the initial state also has an output under the usual convention. Thus, length n gives n Mealy outputs but may give n+1 Moore outputs when the initial value is shown.
Behavioural equivalence means that every input word gives the same observable output after this convention is aligned. Drawings and state counts need not match. Moore Machine Explained: Output Mapping, Worked Trace and Exam Traps owns the single-machine 01 suffix detector and its n-versus-n+1 timing; this article focuses on the two-state Mealy detector, incoming-output splitting, and reversing the conversion. Theory Of Computation / Automata Theory is the focused learning route.
Start with a two-state Mealy detector for the pattern 01
Consider a Mealy machine with input and output alphabets {0,1}. It emits 1 exactly when the current symbol completes 01; otherwise it emits 0. Initial state A means the previous symbol is not 0, or no symbol has been read. State B means the previous symbol is 0.
Present state | Input | Next state | Output |
|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Only B --1/1--> A completes 01. Input 001 follows A -> B -> B -> A and emits 001; 111 stays in A and emits 000.
The conversion difficulty is destination A. The edge A --1/0--> A enters it with output 0, but B --1/1--> A enters it with output 1. One Moore state cannot carry both values.
Convert Mealy to Moore by splitting states on incoming outputs
Use this rule in order:
Group transitions by
(destination state, emitted output)and create one Moore copy per distinct pair.Inherit the underlying Mealy state's outgoing behaviour, but redirect each edge to the copy matching that edge's output.
Add a dummy initial marker to align the missing pre-input Mealy output.
Destination A has incoming output set {0,1}, so it becomes A0 with output 0 and A1 with output 1. These copies remember the output used to enter underlying state A. Destination B has incoming output set {0}, so it becomes only B0 with output 0. There is no B1.
Let I be the initial marker with neutral output epsilon, ignored during comparison. If every formal state output must belong to Delta, treat I as display-only and compare after the first symbol.
State | State output | On | On |
|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Both A copies inherit underlying state A's outgoing behaviour. Their suffixes preserve the different outputs on their incoming transitions.
The partition creates three output-bearing states: A0, A1, and B0. Adding I gives four displayed states. If a count excludes the dummy marker, answer three and state the convention.

Prove equivalence with a prefix-by-prefix output trace
For input 0101, the Mealy machine follows A -> B -> A -> B -> A. Its transition outputs are 0,1,0,1, so the output word is 0101. The two 1 values mark the occurrences of 01 ending at input positions 2 and 4.
The converted Moore machine follows I -> B0 -> A1 -> B0 -> A1. Its state outputs are epsilon,0,1,0,1. Dropping the initial epsilon leaves 0101, exactly the Mealy result. A second check with input 101 gives Mealy output 001 and Moore sequence epsilon,0,0,1, which also matches after alignment.
After every non-empty prefix, the reached Moore state's output equals the last Mealy transition's output, and both machines correspond to the same unsplit state, A or B. The base case follows from I's first edge, and each redirected transition preserves the claim. This invariant proves equality for every input. Input 01 exposes a conversion that labels both A copies 0: Mealy emits 01, but the wrong Moore machine emits 00 after alignment.

Convert Moore back to Mealy, then merge only when behaviour permits
For the reverse conversion, keep each Moore transition p --x--> q and label its Mealy edge x/lambda(q). Use the destination state's output. The source output would shift timing by one step.
Moore source | Mealy transitions written as input to next/output |
|---|---|
|
|
|
|
|
|
|
|
Here I, A0, and A1 have identical next-state/output behaviour. Merge them as A and redirect targets of either A copy to A. Rename B0 as B, and the original two-state table returns, including B --1/1--> A.
This does not mean A0 and A1 were mergeable in the Moore machine. Their Moore outputs differ. They become mergeable only after those state outputs have been transferred to the entering Mealy edges.
Conversion traps are usually timing, splitting or equivalence traps
Use this table to locate common errors:
Mistake | Consequence | Repair |
|---|---|---|
Split by outgoing outputs | Wrong copies | Split by destination and incoming output |
Send an edge to any destination copy | Wrong trace | Match the copy suffix to the edge output |
Put the Moore source output on a Mealy edge | One-step shift | Use the destination output |
Compare | False mismatch | Handle the initial Moore output |
Demand identical graphs or state counts | Reject equivalence | Compare every output word |
Every state also needs a transition for each input symbol. Omitting A1 --1--> A0 is an error even when a short trace misses it. Moore and Mealy Machines: Output Tracing, Conversion and Worked Examples owns the parity trace and general conversion comparison; this article uses the 01 detector to work through incoming-output copies and the reverse merge.
Conversion and equivalence questions test the same four decisions
Questions may ask for a trace, converted table, copy count, or shortest counterexample. Here:
Check | Answer |
|---|---|
Output on |
|
Copies required for destination | Two, because the incoming set is |
Copies required for destination | One, because the incoming set is |
Moore target of |
|
Answer 3 when only output-bearing copies count and 4 when the dummy initial marker counts. The stated convention decides.
For practice, use the CS Fundamentals route alongside this worked machine. Exam-specific rules belong to the current notification from the examining authority.
Moore-Mealy conversion: the short version and next step
For Mealy to Moore, inspect incoming outputs, split destinations, redirect edges, align the initial output, and verify a trace. For Moore to Mealy, put destination outputs on entering edges, then merge identical behaviour.
Try input 00101: the Mealy output is 00101, while the Moore sequence is epsilon,0,0,1,0,1. Removing epsilon gives the same word. For a wider preparation plan around this topic, GATE Guidance by Sanchit Sir is the structured next step.
Keep learning
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 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 MCQs: 11 Solved Questions with State-Trace Explanations
Solve 11 Mealy machine MCQs using state tables, edge-output traces and fresh explanations. Each answer shows how to eliminate plausible options.
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.





