Moore Machine Explained: Output Mapping, Worked Trace and Exam Traps

Many learners can follow arrows in a finite-state diagram but still attach an output to the wrong place or return a string of the wrong length. This guide carries one three-state Moore machine from its formal definition through construction, a trace of 01101, Moore-to-Mealy conversion, and minimisation. By the end, you will know what each state means, when each output appears, and how to check an answer without guessing, with CS Fundamentals for Exams & Placements as the broader subject hub.

Moore machine basics: states produce the output

A Moore machine is a tuple M = (Q, Sigma, Delta, delta, lambda, q0). Here, Q is a finite set of states, Sigma is the input alphabet, Delta is the output alphabet, delta: Q x Sigma -> Q is the transition function, lambda: Q -> Delta assigns exactly one output to each state, and q0 is the initial state.

In a diagram, write a state as state/output. An arrow carries only an input symbol. This differs from a DFA acceptor. A DFA accepts or rejects according to whether its final state belongs to F; a Moore machine emits the initial state's output and another output after every transition. An output of 1 does not automatically mean acceptance.

Throughout this example, Sigma = {0,1} and Delta = {0,1}. For input w = a1a2...an, the run is q0,q1,...,qn, where qi = delta(q(i-1),ai). The full output is lambda(q0)lambda(q1)...lambda(qn).

Moore output timing: settle n versus n+1 first

An input of length n = 5 causes five transitions but visits six states when the initial state is counted. The full Moore output therefore contains n + 1 = 6 symbols. Some questions suppress the initial output and report only the five outputs seen after consuming input symbols. Always state the convention before writing the result.

For the worked input 01101, the complete state-output sequence will be 0,0,1,0,0,1, giving 001001. If only the initial state's first 0 is suppressed, the post-input sequence is 01001. Do not remove the last symbol or shift every value left.

The empty input is a useful check. On epsilon, no transition occurs, but the machine remains in q0 with output lambda(q0). The full convention reports one output; the suppressed-initial convention reports an empty transition-output string.

Construct a Moore machine that detects the suffix 01

The requirement is precise: after each bit, output 1 if and only if the prefix processed so far ends in 01; otherwise output 0. This is not a one-time detector. The output returns to 0 when the current suffix stops being 01, and it may become 1 again after a later occurrence.

Use three states:

• A/0 is the start state. The prefix is empty, or it has no pending final 0 and does not end in 01.

• B/0 means the prefix ends in 0.

• C/1 means the prefix ends in 01.

Thus, Q = {A,B,C}, q0 = A, and lambda(A) = 0, lambda(B) = 0, lambda(C) = 1.

These are all 3 x 2 = 6 transitions. Another 0 always leaves a useful pending 0, so it leads to B. Reading 1 from C changes suffix 01 to 11, so the machine returns to A/0.

Worked Moore trace for input 01101

Start at A/0, include the initial output, and consume exactly one symbol at each step.

The six visited states for five input symbols also confirm the n+1 timing rule.

The exact run is A/0 --0--> B/0 --1--> C/1 --1--> A/0 --0--> B/0 --1--> C/1.

Including the initial state, concatenate 0,0,1,0,0,1 to obtain 001001. If the question wants one output after each consumed bit and suppresses the initial output, concatenate rows 1 through 5 to obtain 01001. Output 1 appears after prefixes 01 and 01101, exactly the two processed prefixes ending in 01.

Two semantic checks confirm the arrows. Prefix 011 ends at A/0, and its last two bits are 11, so its output is correctly 0. The complete input ends at C/1, and its last two bits are 01, so its output is correctly 1.

Convert the worked Moore machine to Mealy form

For every Moore transition p --a--> q, label the corresponding Mealy edge a/lambda(q). The output comes from the destination state. Applying that rule to all six edges gives:

• A --0/0--> B and A --1/0--> A

• B --0/0--> B and B --1/1--> C

• C --0/0--> B and C --1/0--> A

Trace 01101 through the edge labels: 0,1,0,0,1. The Mealy output is therefore 01001. It matches the Moore machine's post-input output, not the full 001001, because a Mealy edge cannot emit the Moore initial-state output before any input arrives.

Copying the source state's output onto an edge would shift the behaviour. It is not the correct conversion. See Moore vs Mealy Machines: GATE Conversion and Minimization for a fuller comparison, but keep the destination-output rule fixed here.

Minimise a Moore machine by output first

Begin with groups of states having equal outputs, not accepting and non-accepting groups. Here, P0 = {{A,B},{C}} because lambda(A) = lambda(B) = 0, while lambda(C) = 1. State C can never merge with either zero-output state.

Now compare ordered destination-group signatures for inputs (0,1). Relative to P0, state A has signature ({A,B},{A,B}), while B has ({A,B},{C}). Their destinations differ on input 1, so split them. Since C is already alone, the stable partition is P1 = {{A},{B},{C}}.

A second refinement makes no further change, which is the stopping condition. In direct terms, C differs immediately by output. Suffix 1 distinguishes A from B: A --1--> A/0, but B --1--> C/1. No pair is equivalent, so the three-state machine is already minimal and its quotient machine still has three states.

Moore machine exam patterns and traps

Possible question forms include reading a diagram to produce an output string, completing a transition and output table, designing a prefix or suffix detector, deciding between output lengths n and n+1, converting between Moore and Mealy forms, and minimising through output-compatible partitions.

Keep these corrections beside the worked values:

• Output written on an edge: in a Moore machine, read the output from the destination state after the move.

• 01001 reported without a convention: say explicitly that the initial 0 was suppressed.

• C/1 treated as accepting: 1 is an output, not an acceptance mark.

• A and B merged because both output 0: input 1 distinguishes them.

• Output kept at 1 after the third bit of 011: C --1--> A/0, so it becomes 0.

For a final check, count one transition for every state-input pair, confirm every state's output, trace every input symbol, and read outputs from the states visited. Then compare the final two bits with the suffix requirement. For 01101, the final suffix is 01, so the last output must be 1.

Moore machine short version and next study step

• Moore outputs belong to states.

• The initial state has an output.

• A full output for an n-symbol input has n+1 values.

• Construction begins by giving every state a precise meaning.

• Minimisation first separates states with different outputs.

For 01101, the machine visits A,B,C,A,B,C, returns full output 001001 and post-input output 01001, and is minimal with three states. Study Theory Of Computation / Automata Theory for focused practice, or Zero to Hero, Complete CS Course for several CS subjects. Theory of Computation maps the subject. Retrace 01101 and explain why only prefixes 01 and 01101 produce 1.