|
In the theory of computation, a Mealy machine is a finite state machine where the outputs are determined by the current state and the input. This means that the state diagram will include an output signal for each transition edge. For example, in going from a state 1 to a state 2 on input '0', the output might be '1' (its edge would be labelled 0/1). In contrast, the output of a Moore finite state machine depends only on the current state and does not depend on the current input. However, every Mealy machine is equivalent to a Moore machine whose state is the Cartesian product of the Mealy machine's current and previous states.
The name "Mealy machine" comes from that of their promoter: G. H. Mealy, a state machine pioneer, who wrote A Method for Synthesizing Sequential Circuits, Bell System Tech. J. vol 34, pp. 1045–1079, September 1955.
Formal definition
A Mealy machine is a 6-tuple,
(S, Σ, Λ, T, G, s), consisting of
- a finite set of states (S)
- a finite set called the input alphabet (Σ)
- a finite set called the output alphabet (Λ)
- a transition function (T : S × Σ → S).
- an output function (G : S × Σ → Λ).
- a start state (s ∈ S)
Example
The machine below is a 1-Timed Delay machine and would generate an output string of 0x0x1...xn-1 for an input string of x0x1...xn. S0 is the start state.
|
