Mealy machine

A Mealy automaton is a deterministic finite automaton whose output depends on its state and (in contrast to a Moore automaton ) on its input. This clearly means that each edge in the state diagram is assigned an output value. The name goes back to George H. Mealy , who advocated the use of this expression.

Formal definition

A Mealy automaton can be defined as 6 tuples : ${\displaystyle {\mathcal {A}}=\left(Q,\Sigma ,\Omega ,\delta ,\lambda ,q_{0}\right)}$

1. ${\displaystyle Q}$is a finite set of states ( ). Instead is also often used. ${\displaystyle \left|Q\right|<\infty }$ ${\displaystyle Q}$ ${\displaystyle Z}$
2. ${\displaystyle \Sigma }$is the input alphabet, . ${\displaystyle \left|\Sigma \right|<\infty }$
3. ${\displaystyle \Omega }$is the output alphabet . ${\displaystyle \left|\Omega \right|<\infty }$
4. ${\displaystyle \delta \colon Q\times \Sigma \rightarrow Q}$ is the transition function.
5. ${\displaystyle \lambda \colon Q\times \Sigma \rightarrow \Omega }$is the output function.
   Occasionally a more compact notation is chosen and both functions are combined into a state transition function . ${\displaystyle \zeta \colon Q\times \Sigma \rightarrow \Omega \times Q}$
6. ${\displaystyle q_{0}\in Q}$is the start state. Instead is often or used. This starting state is marked with a double border or a double arrow. ${\displaystyle q_{0}}$ ${\displaystyle z_{0}}$ ${\displaystyle S_{0}}$

example

The automaton described by the following state diagram outputs its input with a delay, i. H. for an input x ₀ x ₁ ... x _{n, it} generates the output 0 x ₀ x ₁ ... x _n-1 . The edge labeling 0/1 means that if a zero is entered, a one is output in addition to the change in status. S denotes the respective state.

Connection with Moore machine

Mealy and Moore machines can be converted into one another. For example, if you want to convert a Mealy machine into a Moore machine, you can proceed in the following three steps:

Step 1: write output to the nodes

For each edge, the output is transferred to the state on which the edge ends. Usually there are different output values ​​in one state node.

Step 2: Split the nodes and move incoming edges

The states are multiplied so that only one output value is assigned to each state; then you reassign incoming edges to the new states according to the output values.

Step 3: multiply outgoing edges

Finally you have to copy all outgoing edges of the original states and append them to the states from step 2.

The output of the Moore automaton so constructed is equivalent to that of the original Mealy automaton.

See also

• Moore machine
• Deterministic finite automaton

literature

• GH Mealy: A Method for Synthesizing Sequential Circuits , Bell System Tech. J. 34 , pp. 1045-1079, September 1955.
• Fricke, Digitaltechnik, Chapter 8 "Synchronous Switchgear" up to and including 8.4. ISBN 978-3-8348-1783-9
• Reichardt, Textbook Digital Technology, Chapter 12 "Design of synchronous state machines". ISBN 978-3-11-047800-6