Màquina de Mealy

De Viquipèdia
Salta a la navegació Salta a la cerca
El diagrama d'estats d'una màquina de Mealy simple

A la teoria de la computació, una Màquina de Mealy és un tipus de màquina d'estats finits que genera una sortida en funció de l'estat actual i una entrada. Això significa que el Diagrama d'estats inclourà dos senyals d'entrada i sortida per a cada línia de transició. En contrast, la sortida d'una màquina de Moore d'estats finits (l'altre tipus) depèn només de l'estat actual de la màquina, atès que les transicions no tenen entrada associada. No obstant això, per a cada Màquina de Mealy hi ha una màquina de Moore equivalent els estats són la unió dels estats de la màquina de Mealy i el Producte cartesià dels estats de la màquina de Mealy i l'alfabet d'entrada.

El nom "Màquina de Mealy" ve del promotor del concepte: G. H. Mealy, un pioner de les màquines d'estats, qui va escriure Un Mètode per a sintetitzar Circuits seqüencials , Bell System Tech J. vol 34, pp. 1045-1079, September 1955.

Les màquines de Mealy subministren un model matemàtic rudimentari per a les màquines de xifrat. Atès l'alfabet d'entrada i sortida de l'alfabet Llatí, per exemple, llavors una màquina de Mealy pot ser dissenyada per donar-li una cadena de lletres (una seqüència d'entrades), això pot processar en un string xifrat (una seqüència de sortides). No obstant això, encara que es podria probablement utilitzar un model de Mealy per descriure una Màquina Enigma, el diagrama d'estats seria massa complex per subministrar mitjans factibles de dissenyar màquines de xifratge complexes.


Definició formal[modifica]

Una màquina de Mealy és una 6-tupla, (S, S0, Σ, Λ, T, G), formada per:

  • Un conjunt finit d'estats (S)
  • Un estat inicial (S0) que és un element de S
  • Un conjunt finit anomenat alfabet entrada (Σ)
  • Un conjunt finit anomenat alfabet sortida (Λ)
  • Una funció de transicions (T: S × ΣS)
  • Una funció de sortida (G: S × ΣΛ)

Vegeu també[modifica]