Mealy machine
Encyclopedia
In the theory of computation
, a Mealy machine is a finite-state machine whose output values are determined both by its current state
and the current inputs. The outputs change asynchronously with respect to the clock, meaning that the outputs change at unpredictable times, making timing analysis harder. (This is in contrast to a Moore machine
, whose output values are determined solely by its current state.)
In some formulations, the transition and output functions are coalesced into a single function (T : S × Σ → S × Λ).
for a Mealy machine associates an output value with each transition edge (in contrast to the state diagram for a Moore machine, which associates an output value with each state).
, for example, then a Mealy machine can be designed that given a string of letters (a sequence of inputs) can process it into a ciphered string (a sequence of outputs). However, although one could use a Mealy model to describe the Enigma
, the state diagram would be too complex to provide feasible means of designing complex ciphering machines.
Theory of computation
In theoretical computer science, the theory of computation is the branch that deals with whether and how efficiently problems can be solved on a model of computation, using an algorithm...
, a Mealy machine is a finite-state machine whose output values are determined both by its current state
State (computer science)
In computer science and automata theory, a state is a unique configuration of information in a program or machine. It is a concept that occasionally extends into some forms of systems programming such as lexers and parsers....
and the current inputs. The outputs change asynchronously with respect to the clock, meaning that the outputs change at unpredictable times, making timing analysis harder. (This is in contrast to a Moore machine
Moore machine
In the theory of computation, a Moore machine is a finite-state machine, whose output values are determined solely by its current state.-Name:The Moore machine is named after Edward F...
, whose output values are determined solely by its current state.)
History
The Mealy machine is named after George H. Mealy, who presented the concept in a 1955 paper, “A Method for Synthesizing Sequential Circuits”.Formal definition
A Mealy machine is a 6-tuple, (S, S0, Σ, Λ, T, G), consisting of the following:- a finite set of statesState (computer science)In computer science and automata theory, a state is a unique configuration of information in a program or machine. It is a concept that occasionally extends into some forms of systems programming such as lexers and parsers....
(S) - a start state (also called initial state) S0 which is an element of (S)
- a finite set called the input alphabet (Σ)
- a finite set called the output alphabet (Λ)
- a transition functionFunction (mathematics)In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
(T : S × Σ → S) mapping pairs of a state and an input symbol to the corresponding next state. - an output function (G : S × Σ → Λ) mapping pairs of a state and an input symbol to the corresponding output symbol.
In some formulations, the transition and output functions are coalesced into a single function (T : S × Σ → S × Λ).
Diagram
The state diagramState diagram
A state diagram is a type of diagram used in computer science and related fields to describe the behavior of systems. State diagrams require that the system described is composed of a finite number of states; sometimes, this is indeed the case, while at other times this is a reasonable abstraction...
for a Mealy machine associates an output value with each transition edge (in contrast to the state diagram for a Moore machine, which associates an output value with each state).
Simple
Simple Mealy machine has one input and one output. Each transition edge is labeled with the value of the input (shown in red) and the value of the output (shown in blue). The machine starts in state Si. (In this example, the output is the exclusive-or of the two most-recent input values; thus, the machine implements an edge detector, outputting a one every time the input flips and a zero otherwise.)Applications
Mealy machines provide a rudimentary mathematical model for cipher machines. Considering the input and output alphabet the Latin alphabetLatin alphabet
The Latin alphabet, also called the Roman alphabet, is the most recognized alphabet used in the world today. It evolved from a western variety of the Greek alphabet called the Cumaean alphabet, which was adopted and modified by the Etruscans who ruled early Rome...
, for example, then a Mealy machine can be designed that given a string of letters (a sequence of inputs) can process it into a ciphered string (a sequence of outputs). However, although one could use a Mealy model to describe the Enigma
Enigma machine
An Enigma machine is any of a family of related electro-mechanical rotor cipher machines used for the encryption and decryption of secret messages. Enigma was invented by German engineer Arthur Scherbius at the end of World War I...
, the state diagram would be too complex to provide feasible means of designing complex ciphering machines.