Mealy machine

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

Formal definition

A Mealy machine can be defined as a 7- tuple:

  • Is a finite set of states (). Instead is also often used.
  • Is the input alphabet.
  • Is the output alphabet.
  • Is the transfer function.
  • Is the output function. Occasionally, a more compact notation is chosen and combined both functions into a state transition function.
  • Is the start state. Instead is also often used or. This launch condition is characterized by a double border or a double arrow.
  • Is a (finite ) set of possible states accepted ( = final amount ). When the machine stops in a state of after reading the input word, as part of the language. Instead is also often used. To some extent, also completely waives, and whether a word is an element of the language of the automaton is determined only by the output.

Example

The machine described by the following state diagram are its input from delay, ie to an input x0x1 ... xn generate the output 0x0x1 ... xn -1. Here, the edges labeled 0 /1 that in addition to the change in the state a one is output when you enter a zero. S denotes the respective state.

Connection with Moore machine

Mealy and Moore automata can be converted into each other. If you want, for example, can transform a Mealy machine into a Moore machine to proceed in the following three steps:

Step 1: write to the output node

For each edge, the output is transferred to the state in which the edge ends. These are usually available different output values ​​in a state node.

Step 2: split nodes and reassign incoming edges

The states are multiplied, so that each state, an output value is assigned to no more than; then it depends incoming edges to the corresponding output values ​​to the new states.

Step 3: multiply Outgoing edges

Last you have to copy all outgoing edges of the original states and attach it to the states from step 2.

The output from the thus constructed Moore machine is equivalent to that of the original Mealy machines.

Finite-state machine Deterministic finite automaton
560592
de