Next: Moore machines
Up: Nets with circles and
Previous: Nets with circles and
Contents
Index
Mealy machines
Mealy machines (Hopcroft and Ullman (1979, 42),
Salomaa (1973, 31)) are finitestate
machines that act as transducers or translators, taking a
string
on an input alphabet and producing a string of
equal length on an output alphabet. Formally, a
Mealy machine is a sixtuple

(3.2) 
where

is a finite set of states;

is a finite input alphabet;

is a
finite output alphabet;

is the nextstate
function, such that a machine in state , after reading
symbol , moves to state
.

is the output
function, such that a machine in state , after reading
symbol , writes symbol
; and
 is the initial state in which the machine
is found before the first symbol of a
string is processed.
As an example, let
such that:
 , .



,
,

,
,
This machine, which may also be represented as in figure 2.2,
outputs an E if the number of 1s read so far is even and an O if it is odd; for example, the translation of 11100101 is OEOOOEEO.
Figure 2.2:
A Mealy machine that outputs an E if the number of 1s read so far is
even and an O if it is odd. Transition labels are
where
is the input and
is the output.

Next: Moore machines
Up: Nets with circles and
Previous: Nets with circles and
Contents
Index
Debian User
20020121