|
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. Computation can be defined as finding a solution to a problem from given inputs by means of an algorithm. ...
Fig. ...
State diagrams are used to graphically represent finite state machines. ...
Moore model: control of an elevator door In the theory of computation, a Moore machine is a finite state automaton where the outputs are determined by the current state alone (and not on the input). ...
In set theory and other branches of mathematics, the union of a collection of sets is the set that contains everything that belongs to any of the sets, but nothing else. ...
In mathematics, the Cartesian product (or direct product) of two sets X and Y, denoted X × Y, is the set of all possible ordered pairs whose first component is a member of X and whose second component is a member of Y: The Cartesian product is named after René Descartes...
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, S0, Σ, Λ, T, G), consisting of In mathematics, a tuple is a finite sequence of objects (a list of a limited number of objects). ...
- 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 × Σ → Λ)
Partial plot of a function f. ...
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. -
 Image File history File links A state diagram for a Mealy machine created by me. ...
Cryptography A Mealy machine can be used as a cryptographic 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.
See also |
Feeds |
Contact