Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 59 ยท Finite Automata

Mealy and Moore Machines

Learn Mealy and Moore machines, finite state transducers that produce output, how they differ, how to convert between them, with a binary adder and Python code.

A DFA answers a single yes-or-no question about its whole input. Many real systems need something richer: they must produce an output while they read, such as a stream of bits, a signal on a wire or a response to every key press. Finite automata with output are called finite state transducers, and the two classic kinds are the Mealy machine and the Moore machine, named after their inventors. They are the standard model of sequential logic in digital hardware.

Moore machine: output depends on the state

A Moore machine is a 6-tuple (Q, ฮฃ, ฮ”, ฮด, ฮป, q0):

  • Q, ฮฃ, ฮด and q0 are as in a DFA (states, input alphabet, transition function, start state). There are no accepting states.
  • ฮ” is the output alphabet.
  • ฮป : Q โ†’ ฮ” is the output function: each state has an output symbol.

When the machine enters a state it emits that state's output. Starting in q0 it emits ฮป(q0) before reading anything, so for an input of length n the output has length n + 1.

Mealy machine: output depends on the transition

A Mealy machine has the same tuple, except the output function is ฮป : Q ร— ฮฃ โ†’ ฮ”: the output is attached to a transition. On reading symbol a in state q, it emits ฮป(q, a) and moves to ฮด(q, a). For an input of length n the output has length n, and the output can react to the current input symbol immediately (in the same step), which makes Mealy machines more responsive.

Mealy diagrams label arrows input/output; Moore diagrams label each state name/output.

Feature Moore Mealy
Output function ฮป(state) ฮป(state, input)
Output length for input of length n n + 1 n
Reacts to input one step later in the same step
Typical number of states often larger often smaller
Output glitches in hardware fewer (outputs change only on clock edges) possible, since inputs affect outputs directly

Example: a Mealy machine that complements bits

The machine below has one state and flips every bit: 0/1 and 1/0. It is a one-state Mealy machine; as a Moore machine it would need extra states.

Python Mealy and Moore machine simulators

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The Moore output starts with 0 (the output of the start state) and has one extra symbol, exactly as the n + 1 rule predicts.

Example: a serial binary adder

Real hardware adds binary numbers one bit at a time, least significant bit first, remembering only the carry. The machine reads pairs of bits (x, y) and writes one sum bit per step. Two states (carry 0 and carry 1) are enough, no matter how long the numbers are, which is exactly why a finite machine can add arbitrary-length numbers.

flowchart LR
    c0(("c0")) -->|"00/0, 01/1, 10/1"| c0
    c0 -->|"11/0"| c1(("c1"))
    c1 -->|"00/1"| c0
    c1 -->|"01/0, 10/0, 11/1"| c1

Each arrow is labeled xy/sum. State c0 means "no carry", c1 means "carry 1". After the last pair the carry is flushed with an extra 00 input.

Python Serial binary adder as a Mealy machine

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two-state machine gives the same sums as Python's own integers. Hardware designers build exactly this circuit and call it a serial adder.

Converting between the two

The models are equivalent in power, up to the one-symbol difference in output length.

Moore to Mealy: assign to each transition the output of the state it enters: ฮป_Mealy(q, a) = ฮป_Moore(ฮด(q, a)). The Mealy output is the Moore output without its first symbol. The number of states stays the same.

Mealy to Moore: the output now has to come from the state, so split each state by the output on its incoming transitions. A Mealy state q whose incoming transitions carry outputs {x, y} becomes two Moore states (q, x) and (q, y). The start state needs a chosen initial output. This may increase the number of states up to |Q| ร— |ฮ”|.

Python Convert a Moore machine to a Mealy machine and compare

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Where they are used

  • Digital circuits: controllers, counters, serial adders and traffic-light logic are Mealy/Moore machines built from flip-flops.
  • Lexers and protocol handlers: a machine that emits a token or response as it consumes input is a transducer.
  • Text processing and compression: simple encoders (like run-length or finite-state transducers for spelling and morphology) are Mealy machines.

Mealy and Moore machines compute functions from strings to strings, where a DFA computes a yes/no answer. A DFA is the special case where the output is "accept/reject" attached to each state, which is a Moore machine with two outputs.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In a Moore machine, the output is determined by...

    A Moore machine has ฮป : Q โ†’ ฮ”. Each state carries its own output symbol.
  2. 2. A Mealy machine reads an input of length 6. How many output symbols does it produce?

    A Mealy machine emits one output per transition, so the output length equals the input length. A Moore machine would produce 7.
  3. 3. Why does a serial binary adder need only two states?

    At each bit position, the sum depends only on the two input bits and the carry from the previous position.
  4. 4. When converting a Mealy machine to a Moore machine, why can the number of states grow?

    A Moore output depends only on the state, so a Mealy state reached with different outputs must be split into one copy per output.

Summary

  • Mealy and Moore machines are DFAs with output: they compute functions from input strings to output strings.
  • Moore: output per state, output length n + 1. Mealy: output per transition, length n, often fewer states and a faster reaction.
  • A Moore machine converts to a Mealy machine with the same states; the reverse may multiply states by up to |ฮ”|.
  • They model sequential circuits and simple string transformers like the serial adder.

Next: Regular Expressions and Regular Languages