A Mealy machine is a finite-state machine that produces an output determined jointly by its current state and the input it receives. Each input symbol causes a state transition and produces an output symbol, so outputs are conventionally attached to transitions rather than to states. Mealy machines are used to describe digital controllers, communication protocols, sequence detectors, and other systems that process inputs using a finite amount of memory. The model is named after George H. Mealy, whose 1955 paper “A Method for Synthesizing Sequential Circuits” presented this approach to sequential circuit design.
Formal definition
A deterministic Mealy machine is commonly defined as a six-tuple
where:
- is a finite, nonempty set of states.
- is a finite input alphabet.
- is a finite output alphabet.
- is the transition function.
- is the output function.
- is the initial state.
For an input sequence , the states and outputs satisfy
Thus, the output depends on the state before the transition and the input symbol responsible for that transition.
In the standard definition, both functions are total: every state–input pair has a specified next state and output. Partial Mealy machines leave some pairs undefined, for example when describing an incompletely specified controller or an interface with restricted legal inputs.
A standard Mealy machine produces exactly one output symbol per input symbol. Its input–output behavior therefore defines a length-preserving function
where and denote the sets of finite strings over the respective alphabets. The empty input produces the empty output. Unlike a recognizer for a formal language, a Mealy machine does not inherently require accepting or rejecting states.
Representation and operation
State diagrams and tables
In a state diagram, states are vertices and transitions are directed edges. An edge labeled means: on input , produce output and follow the edge to its destination state.
A transition table gives the same information by listing, for every state and input, a pair consisting of the next state and the output. These representations separate the machine’s two central operations:
- Updating memory: choosing the next state.
- Producing a response: choosing the output for the current input.
The state summarizes the relevant input history. Different histories may lead to the same state when their distinctions no longer matter to future behavior.
Example: detecting the sequence 101
Consider a machine that reads a stream of binary symbols and outputs whenever the latest input completes the pattern . It outputs otherwise, and permits overlapping occurrences.
Three states suffice:
- : no nonempty suffix of the input so far matches a proper prefix of .
- : the longest such matching suffix is .
- : the longest such matching suffix is .
The initial state is .
| Current state | Input 0: next state/output | Input 1: next state/output |
|---|---|---|
For the input , the output is . After detecting , the machine enters , because the final can also begin another occurrence. This preserves the information needed to recognize overlapping matches without storing the entire input history.
Relationship to other computational models
Moore machines
A Moore machine differs in how it determines outputs. Its output function depends only on the current state:
In a Mealy machine, the output function depends on both state and input:
Consequently, a Mealy machine can produce different outputs for different inputs while remaining in the same state. A Moore machine must use states with different output labels to represent such differences.
The two models can represent the same finite-state input–output behavior when output timing and the initial output are aligned appropriately:
- A Moore machine can be converted into a Mealy machine by labeling each transition with the output of its destination state, if outputs are compared after each input is processed.
- A Mealy machine can be converted into a Moore machine by splitting destination states according to the outputs on incoming transitions. The resulting states can be represented as pairs , recording both the destination state and the output just produced.
The second construction can increase the number of states. It also requires an explicit convention for the Moore machine’s output before the first input, because a standard Mealy machine has no corresponding initial output.
Claims that one model responds “one clock cycle faster” depend on implementation and observation conventions, not on an unconditional difference in computational power.
Finite-state transducers and Turing machines
A Mealy machine is a restricted finite-state transducer. More general transducers may produce empty strings or multiple output symbols on a transition, include transitions that consume no input, or allow nondeterministic choices.
Its memory is limited to its finite state set. Unlike a Turing machine, it has no unbounded work tape. It cannot, for example, maintain an exact counter of arbitrary size or recognize arbitrarily nested structures without a fixed bound.
Despite this limitation, Mealy machines can process streams of unbounded length: the restriction concerns retained memory, not how many input symbols may be processed.
Digital circuit implementation
In synchronous hardware, a Mealy controller is commonly implemented using:
- A state register, typically built from flip-flops.
- Combinational logic that computes the next state from the current state and inputs.
- Combinational logic that computes outputs from the current state and inputs.
For states, a binary state encoding requires at least
state bits. Other encodings, including one-hot encoding, trade additional storage elements for different logic and timing characteristics.
In an unregistered Mealy implementation, an input change can affect an output before the next clock edge, after propagation through the output logic. This can provide a direct response to an input, but it also exposes outputs to input instability and combinational glitches. Asynchronous inputs require suitable synchronization or interface circuitry; the abstract machine itself does not model metastability or electrical timing.
Registering the outputs changes their timing and must be reflected in the specification. Whether a Mealy or Moore implementation is preferable depends on state count, logic depth, timing constraints, and interface requirements. Neither model is inherently superior for every circuit.
Electronic design automation tools can synthesize hardware descriptions of these controllers into registers and logic gates.
Equivalence and minimization
Two states of a deterministic Mealy machine are behaviorally equivalent if every finite future input sequence produces the same output sequence from either state. Equivalent states may be merged without changing observable behavior.
A standard minimization procedure uses partition refinement:
- Remove states unreachable from the initial state.
- Group states that produce the same output for every individual input symbol.
- Split a group whenever two of its states transition, on the same input, into different groups.
- Repeat until no further split is possible.
The resulting equivalence classes become the states of a reduced machine. For reachable, completely specified deterministic Mealy machines, the minimal realization of a given behavior is unique up to renaming states.
Machine equivalence can also be checked by exploring pairs of states in a product construction. If a reachable pair produces different outputs for some input, the input sequence leading to that discrepancy is a distinguishing test. This supports formal verification and the comparison of implementations with their specifications.
Applications and limitations
Mealy machines are useful when responses depend on both a finite interaction history and the next input. Applications include:
- Sequence detection: recognizing patterns in serial data streams.
- Digital control: generating control signals from a controller’s state and current inputs.
- Protocol modeling: describing how a participant responds to messages in different protocol states.
- Software testing: generating input sequences and checking expected output traces.
- Interface modeling: representing bounded request–response behavior.
They can also serve as models for model checking, although practical specifications often add data variables, timing constraints, or environmental assumptions.
The principal limitation is finite memory. Encoding many independent variables directly as states can produce a very large state space. Moreover, a basic Mealy machine does not express real-time deadlines, probability, continuous physical quantities, or unrestricted concurrency. Such features require extensions or other modeling frameworks.
The interpretation of an input or output symbol is another important modeling choice. A symbol may represent a single electrical bit, a vector of signals, or an abstract event such as receiving a message. Correctness at the abstract level does not by itself establish that electrical timing, message transport, or environmental assumptions are satisfied.