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

Updated 29 Oct 20266 min read
Moore and Mealy Machine Conversion: Equivalence, State Splitting and a Worked Trace

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

A

0

B

0

A

1

A

0

B

0

B

0

B

1

A

1

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:

  1. Group transitions by (destination state, emitted output) and create one Moore copy per distinct pair.

  2. Inherit the underlying Mealy state's outgoing behaviour, but redirect each edge to the copy matching that edge's output.

  3. 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 0

On 1

I

epsilon

B0

A0

A0

0

B0

A0

A1

1

B0

A0

B0

0

B0

A1

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.

Diagram showing a Mealy 01 detector, incoming-output partition into A0, A1 and B0, and the resulting Moore machine with an initial epsilon marker.

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.

Trace table for input 0101 aligning Mealy edge outputs 0101 with Moore states I, B0, A1, B0, A1 after ignoring initial epsilon.

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

I

0 -> B0/0, 1 -> A0/0

A0

0 -> B0/0, 1 -> A0/0

A1

0 -> B0/0, 1 -> A0/0

B0

0 -> B0/0, 1 -> A1/1

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 n outputs with n+1 unaligned outputs

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 101

001

Copies required for destination A

Two, because the incoming set is {0,1}

Copies required for destination B

One, because the incoming set is {0}

Moore target of B --1/1--> A

A1

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.