Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

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):

    1. 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).
    2. 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}.

  1. Idea: machine must remember previous bit or a special start marker.
  2. States: S (start, no previous), P0 (previous = 0), P1 (previous = 1). Initial state q0 = S.
  3. 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.
  4. 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):

  1. 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).
  2. 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).
  3. 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).
  4. 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

  1. Define a Mealy machine and give its output-function signature.
  2. Why does converting a Mealy machine to a Moore machine often increase the number of states?
  3. 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?