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

Updated 30 Oct 20266 min read
Mealy Machine Explained: Worked Output Traces and Moore Conversion

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 0: next, output

Input 1: next, output

A

A, 0

B, 0

B

C, 0

B, 0

C

A, 0

B, 1

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.

Three-state Mealy diagram for overlapping 101 detection. A starts the machine; B tracks suffix 1; C tracks suffix 10; the C-to-B edge emits 1.

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

1

A

A --1/0--> B

0

B

2

1

B

B --1/0--> B

0

B

3

0

B

B --0/0--> C

0

C

4

1

C

C --1/1--> B

1

B

5

0

B

B --0/0--> C

0

C

6

1

C

C --1/1--> B

1

B

7

0

B

B --0/0--> C

0

C

8

1

C

C --1/1--> B

1

B

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.

Eight-step table traces input 11010101 through states A, B, and C, emitting 00010101 and marking overlapping 101 matches at positions 2-4, 4-6, and 6-8.

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 0

On 1

A0

0

A0

B0

B0

0

C0

B0

B1

1

C0

B0

C0

0

A0

B1

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 1/0 as output/input

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 C --1/1--> B to A

Overlapping occurrences are missed

Preserve the final 1 in state B

Shifting the output by one position

Input and output bits no longer align

Emit while taking the current edge

Marking B as an accepting state

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:

  1. Read the output for a supplied input string.

  2. Fill a missing edge or output in a transition table.

  3. Design a sequence detector from prefix memory.

  4. Convert Mealy to Moore and account for every split state.

  5. 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.