Sequential Machines
Mealy vs Moore Machines
Both machines turn an input stream into an output stream, one symbol at a time — they just disagree about whether output belongs to transitions or to states.
Mealy and Moore machines both add an output alphabet to a finite automaton: instead of deciding accept/reject, they produce one output symbol per input symbol, turning the machine into a simple sequential transducer. They differ only in where the output function lives.
Mealy: output on transitions
A Mealy machine is (Q, Σ, Δ, δ, λ, q₀), where λ: Q × Σ → Δ assigns an output to each transition. The output for a given input symbol depends on both the current state and the symbol itself, so it can react within the same step. Below, each state tracks the parity of 1s seen so far, and every transition outputs the new running parity: 1 for odd, 0 for even.
Feed it 101: reading the first 1 outputs 1 (odd so far) from q0; reading 0 outputs 1 again (parity unchanged) from q1; reading the second 1 outputs 0 (back to even) back at q0. Three inputs, three outputs — Mealy machines always produce exactly as many outputs as inputs.
Moore: output on states
A Moore machine is (Q, Σ, Δ, δ, λ, q₀) too, but λ: Q → Δ assigns one fixed output to each state instead — shown here as state/output on each node. Computing the same running parity, the state is the parity, so no transition needs its own label beyond the input symbol.
Because Moore's output only depends on the current state, tracing 101 from the start state's own output (0, before reading anything) gives one extra output compared to the equivalent Mealy machine — n inputs produce n + 1 outputs, one per state visited including the start. Every Mealy machine has an equivalent Moore machine and vice versa; converting between them just shifts where that extra output falls.