Mealy machine
From Free net encyclopedia
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 labeled 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 states are the union of the Mealy machine's states and the Cartesian product of the Mealy machine's states and the input alphabet.
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.
Contents |
Formal definition
A Mealy machine is a 6-tuple, (S, S0, Σ, Λ, T, G), consisting of
- a finite set of states (S)
- a start state S0 which is an element of (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 × Σ → Λ)
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.
Cryptography
A Mealy machine can be used as a criptographic machine. Given an alphabet A, it is said to be possible to process a word from this alphabet into a word from alphabet B if there exists a Mealy machine which does this. Using Matmeatical notation, M - Mealy machine, -> - to process: thus a tuple (M, ->). Clearly there exists a Mealy machine which transforms word from alphabet A to the same word, that is there exists a reflexive Mealy machine: a -> a Also there exists a transitive Mealy machine, that is given two Mealy machines it is possible to construct the third which acts as the the other two connected in series (output from the first is fed into the second and the output from second is output of this Mealy machine): a -> b and b -> c then a -> c These two mathematical qualities introduce preordering on set of words which Mealy machines process. Now we can introduce ordering, that is given a class of words it is said that the words are in the same class if a -> b and b -> a. A word which can only be a -> b, but not b -> a is clealy of higher complexity. So Mealy machines can be used to analyise complexity of words which brings us to cryptography.