Moore and Mealy Machines: Output Tracing, Conversion and Worked Examples

A Moore machine writes output on states, while a Mealy machine writes it on transitions. That one difference changes how you read the first output and perform every conversion. Most wrong answers come from an unstated convention, namely whether the initial state's output counts and which end of an edge supplies a converted output.

Moore and Mealy machines are finite-state transducers

Start with the finite-automaton model. A DFA reads a string and finally answers accept or reject. A Moore or Mealy machine instead translates an input sequence into an output sequence as it runs. If states, alphabets or transition functions need a refresh, revise DFA and NFA fundamentals first.

Both machines can be written as (Q, Sigma, Delta, delta, lambda, q0). Here, Q is the state set, Sigma the input alphabet, Delta the output alphabet, delta the transition function and q0 the initial state. The difference is the output function:

• Moore: lambda: Q -> Delta

• Mealy: lambda: Q x Sigma -> Delta

We use Sigma = {0,1} and Delta = {0,1} throughout. Our Moore trace includes the initial state's output. An input of length n therefore displays n + 1 Moore outputs. For comparison with Mealy, drop that initial output and compare the next n symbols. Mealy produces exactly n outputs. For input epsilon, Moore displays its initial output, while Mealy produces the empty string.

Moore versus Mealy: read the labels before tracing

An equivalent Mealy machine can often keep the Moore states. Mealy-to-Moore conversion may split one original state into several state-output copies, so do not claim every minimal Mealy machine must be smaller.

For a quick notation check, the Moore edge E --1--> O takes the output written on destination state O. The Mealy edge E --1/1--> O emits 1 on that edge. Neither state is an accepting state, because these machines are transducers, not recognisers.

Worked example 1: running parity in both forms

The task is to output 0 after each bit when the number of 1s seen so far is even, and 1 when it is odd. The Moore states are E/0 initially and O/1.

Trace input 10110 without skipping the initial row:

The displayed Moore sequence is 011011. Dropping its initial 0 gives the aligned output 11011.

The equivalent Mealy table places the destination state's output on each edge:

For 10110, the edge outputs are 1, 1, 0, 1, 1, so the Mealy output is 11011. It exactly matches the aligned Moore result.

Conversion rules, including the state-splitting case

For Moore to Mealy, replace every Moore transition q --a--> r with q --a/lambda(r)--> r. Applying this rule to parity gives E --0/0--> E, E --1/1--> O, O --0/1--> O and O --1/0--> E. Moore's initial 0 has no pre-input Mealy edge, which is why alignment ignores it.

For Mealy to Moore, split a destination state once for every distinct output on transitions entering it. Keep only reachable state-output pairs, then redirect each transition to the copy carrying that transition's output.

Consider this Mealy machine, with A initial:

Transitions enter both A and B with outputs 0 and 1. Create A0/0, A1/1, B0/0 and B1/1. Add S/- as a fresh start state whose placeholder output is ignored before input.

Now trace 1011. Mealy follows A -> B -> A -> B -> B and emits 1110. Moore follows S -> B1 -> A1 -> B1 -> B0 and displays -1110. Ignoring the placeholder leaves the same four symbols.

Equivalence, reachability and minimisation

Two machines are behaviourally equivalent when every input gives equal aligned output sequences. The parity trace proves agreement for one string only. The conversion rule proves the transition-by-transition correspondence for every string.

The second example starts with two Mealy states and produces four reachable (state, output) copies, plus the fresh start state. That gives five displayed Moore states before minimisation. In general, |Q| = 2 and |Delta| = 2 allow at most four such pairs, not simply “double the states”, plus a start device when alignment requires it.

Keep conversion and minimisation separate. Build the equivalent machine, remove unreachable copies, then merge only states that have the same present output and equivalent future behaviour. Never merge A0/0 with A1/1, because their outputs differ.

Run that test on the second example. Group the four copies by present output: A0/0 and B0/0 emit 0, while A1/1 and B1/1 emit 1. On input 0 the two A copies both reach A0/0, while the two B copies both reach A1/1, which sits in the other group. Both groups therefore split on the first refinement round, and no two copies merge. Only the start state is negotiable: S/- has exactly the transitions of A0/0, so a convention that reads its placeholder as 0 collapses the machine to four states, and one that keeps the placeholder distinct leaves five. For the refinement procedure written out step by step on a three-state machine, work through Moore vs Mealy machines for GATE.

Common traps and how to repair them

• Initial output: On input 1, Moore parity displays 01; its aligned comparison is the last symbol, 1. Write the convention beside the question.

• Wrong endpoint: O --1--> E/0 becomes O --1/0--> E. The output comes from destination E, not source O/1.

• Incomplete splitting: The second machine needs A0 and A1 because transitions enter A with both outputs. Do not create a state-output copy that no transition can reach.

• Diagram reading: q/1 inside a state means Moore output 1. 0/1 beside an edge means input 0, output 1. Make a short table if a diagram is crowded.

How GATE-style questions test the topic

Common problems ask you to trace an output string, complete a table, convert a machine, count reachable split states or detect a faulty conversion. Try these checks before reading the key:

1. Moore parity on 00: full output 000, aligned output 00.

2. Mealy parity on 110: output 100.

3. Moore O --1--> E/0: Mealy label 1/0.

4. In the A,B conversion, input 10: final Moore state A1/1, aligned output 11.

KnowledgeGate carries more than 40 practice questions on Moore and Mealy machines, covering the basics, Mealy design and conversion. Continue with the focused finite automata MCQs, then widen to the GATE preparation category for the rest of the subject.

Short version and next step

Moore outputs sit on states, Mealy outputs sit on transitions, and equivalent traces match only after handling the initial Moore output consistently. Moore-to-Mealy moves each destination output onto its incoming edge. Mealy-to-Moore may split a state by incoming output and may need a fresh start state.

On paper, redraw parity and trace 01011: the full Moore output is 001101, its aligned output is 01101, and the converted Mealy machine also gives 01101.

For structured subject study, work through the automata sequence in GATE Guidance by Sanchit Sir. Move to timed papers once your traces come out right on the first attempt.