Moore and Mealy machines
Moore and Mealy machines are two kinds of finite-state machines that produce outputs: Moore outputs depend only on states, Mealy outputs depend on state and input; they are equivalent in expressive power but differ in where outputs are produced and in practical state counts.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Moore and Mealy machines are models of finite-state devices that produce outputs while reading input. Engineers use them to design digital controllers, serial-output circuits, protocol handlers, lexical scanners, and simple embedded-state logic where outputs must follow inputs with or without delay.
Key ideas
Q is a finite set of states.
Σ is a finite input alphabet.
Γ is a finite output alphabet.
δ: Q × Σ → Q is the transition function (gives the next state for a state and input).
λ: Q → Γ is the output function (gives the output symbol for each state).
q0 ∈ Q is the initial state. Assumptions: deterministic transition function defined for all Q × Σ.
Mealy machine — A deterministic FSM that produces outputs on transitions. Formal definition (exact): A Mealy machine is a 6-tuple N = (Q, Σ, Γ, δ, λ, q0) where Q, Σ, Γ, δ and q0 are as above but
- δ: Q × Σ → Q is the transition function.
- λ: Q × Σ → Γ is the output function that gives an output symbol for each state and input pair.
Relationship and typical observations:
- In a Mealy machine the output symbol appears together with the transition (so it can react immediately to the current input). In a Moore machine the output is visible as soon as the machine enters a state, so it depends only on the state and may appear to be delayed by one input symbol compared to an equivalent Mealy.
- Equivalence theorem (informal exact statement often used in exams): For every Mealy machine M there exists a Moore machine M' that implements the same input→output behaviour up to a fixed delay of at most one output symbol; and for every Moore machine there exists a Mealy machine with exactly the same input→output sequence (no delay). Conversions are constructive and standard.
Conversions (algorithms universities ask for):
- Moore → Mealy (simple no-delay): Keep the same states Q. Define δ' = δ. Define λ'(q, a) = λ(δ(q, a)) for all q ∈ Q and a ∈ Σ. This Mealy produces, for each input symbol, exactly the Moore output of the destination state reached on that symbol (so the per-input output sequence is identical; no change in number of states).
- Mealy → Moore (standard construction that may increase states): Create new states that encode the destination state plus the output produced upon entering it. One standard construction: for each original state p ∈ Q and for each possible output symbol y ∈ Γ that can appear on some transition into p, create a new state (p, y) with λ((p, y)) = y. Define initial state carefully (Moore must have an output for q0; choose a special start-output or add an initial state producing an appropriate first output if the Mealy had no well-defined first output). For each Mealy transition δ(q, a) = p with output y = λ(q, a), add a Moore transition from state representing current situation to (p, y) on input a. This way the Moore machine outputs y after the transition when it is inside (p, y). Note: this construction may produce up to |Q|·|Γ| states; often fewer in practice because not all outputs occur for every state.
What to draw in diagrams (what examiners expect):
- For a Mealy machine: Draw circles for states labeled q0, q1, ... Mark the initial state with an incoming arrow (no source). Label each directed edge as input/output, for example a/1 meaning on input 'a' the transition fires and produces output '1'.
- For a Moore machine: Draw circles labeled q0/γ0, q1/γ1 where γi is the output of that state. Label edges with inputs only (no outputs on edges). Also draw an incoming arrow to the initial state.
Note on acceptance: Moore and Mealy are transducers (machines that produce output). If you need acceptance by final states, add a set F ⊆ Q and treat acceptance separately (this is not required for output behaviour discussions).
Formulas
M = (Q, Σ, Γ, δ, λ, q0) — Moore machine; Q: states, Σ: input alphabet, Γ: output alphabet, δ: Q×Σ→Q, λ: Q→Γ, q0 ∈ Q.
N = (Q, Σ, Γ, δ, λ, q0) — Mealy machine; δ: Q×Σ→Q, λ: Q×Σ→Γ.
δ(q, a) = p — on state q and input symbol a the next state is p. (No SI units; symbols are sets or functions.)
λ_Moore(q) = y — Moore output function, y ∈ Γ, produced when machine is in state q.
λ_Mealy(q, a) = y — Mealy output function, y ∈ Γ, produced during transition from q on input a.
|Q'| ≤ |Q|·|Γ| — worst-case number of states in the Moore machine produced from a Mealy machine by the standard construction (state blow-up bound).
Worked examples
Example 1 — Design a Mealy machine that outputs 1 whenever the current input bit equals the previous input bit; otherwise output 0. Input alphabet Σ = {0,1}, output Γ = {0,1}.
- Idea: machine must remember previous bit or a special start marker.
- States: S (start, no previous), P0 (previous = 0), P1 (previous = 1). Initial state q0 = S.
- Define transitions and outputs (table):
- From S: on input 0 → go to P0 and output 0 (no previous bit to compare). on input 1 → go to P1 and output 0.
- From P0: on input 0 → stay in P0 and output 1 (same as previous). on input 1 → go to P1 and output 0.
- From P1: on input 1 → stay in P1 and output 1. on input 0 → go to P0 and output 0.
- Trace on input 1 0 1 1 0 (write as 10110):
- Start in S. Read 1: transition S --1/0--> P1, output 0.
- Read 0: P1 --0/0--> P0, output 0.
- Read 1: P0 --1/0--> P1, output 0.
- Read 1: P1 --1/1--> P1, output 1.
- Read 0: P1 --0/0--> P0, output 0. Output sequence: 0 0 0 1 0. Bold final: 00010.
Example 2 — Convert that Mealy machine to an equivalent Moore machine (showing the typical one-symbol delay):
- For each Mealy transition q --a / y--> p, we need a Moore state representing p with output y (so the output produced while in that Moore state equals the Mealy output produced on the transition that entered p).
- From the Mealy in Example 1, the outputs produced on transitions to P0 are either 0 or 1 (both occur), so create Moore states (P0,0) and (P0,1) with outputs 0 and 1 respectively. Similarly for P1 we need (P1,0) and (P1,1). For S (start), on transitions into S none occur, but we need an initial state; choose a start state S0 with output 0 (or a special start-output symbol if specification requires).
- Build transitions: if Mealy has q --a / y--> p, then in Moore add an edge from every Moore state whose first component is q (or from the unique initial Moore state at the start) to (p, y) on input a. Carefully choose the initial Moore state to reflect no previous output; the Moore output sequence will match the Mealy output shifted by one symbol (initial Moore output is produced before any input).
- Trace the same input 10110 and compare: the Moore outputs will be (initial output) followed by Mealy outputs shifted; exam answers should mention the one-symbol delay and initial-output handling.
Example 3 — Moore → Mealy quick conversion: If Moore has states q0/1, q1/0 and δ(q0, a)=q1, δ(q1,a)=q0, then set Mealy outputs to the destination state's Moore output: λ'(q,a)=λ(δ(q,a)). So outputs on transitions equal the Moore output of the state entered on that input; a trace shows the per-input output sequence is identical.
Common mistakes
- Missing that Mealy → Moore may increase states and not proving the upper bound on state count.
- Confusing δ and λ signatures; write their domains and codomains explicitly.
- Omitting the incoming arrow for the initial state in drawings or forgetting to label state outputs in Moore diagrams.
For your exam
Kinds of questions you will see:
- Definitions: Give formal definitions of Moore and Mealy machines with δ and λ signatures.
- Short notes: Differences between Moore and Mealy, advantages/disadvantages, state blow-up.
- Conversions/derivations: Convert a small Mealy to Moore (or vice versa) and show the resulting machine and a trace on an input string.
- Diagrams: Draw Mealy (edges input/output) and Moore (states with outputs) machines for a verbal specification.
- Proof/argument: Prove that every Moore machine can be implemented as a Mealy machine and sketch the constructive proof for Mealy→Moore.
What a full-marks answer includes:
- Formal 6-tuple definition with correct domains and codomains for δ and λ.
- Correct conversion algorithm with reasons (treat initial/output-shift explicitly).
- Correct diagram with labels as described above.
- A correct trace showing each state, input, and output step-by-step.
Quick check
- Define a Mealy machine and give its output-function signature.
- Why does converting a Mealy machine to a Moore machine often increase the number of states?
- How do Moore and Mealy outputs differ in timing for the same logical specification? Answers: 1) A Mealy machine is N=(Q,Σ,Γ,δ,λ,q0) with λ: Q×Σ→Γ. 2) Because Moore outputs are associated to states, we must create separate states for different possible outputs produced on transitions into the same original state (state blow-up up to |Q|·|Γ|). 3) Mealy outputs appear on transitions (immediate with input); Moore outputs are associated to states (appear after entering a state) — so Moore may show a one-symbol delay relative to Mealy.
(Reviewer note: I have stated the standard constructions and examples used in university answers. See verify list below for items I recommend you check for the precise formal treatment and any university-specific conventions.)
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?