Machine de Mealy

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Le diagramme états-transitions d'une machine de Mealy.


En informatique théorique, notamment en théorie des automates, et en théorie de la calculabilité, une machine de Mealy ou automate de Mealy est un automate fini (et plus précisément un transducteur fini) pour lequel les sorties dépendent à la fois de l'état courant et des symboles d'entrée. Cela signifie que l'étiquette de chaque transition est un couple formé d'une lettre d'entrée et d'une lettre de sortie. En particulier, la longueur du mot de sortie est égale à la longueur du mot d'entrée. Cette définition est plus générale que celle des machines de Moore pour lesquelles les valeurs de sortie ne dépendent que de l'état courant. Toutefois, il existe pour chaque machine de Mealy, une machine de Moore équivalente et réciproquement.

Cet automate tient son nom de George H. Mealy, qui a proposé ce modèle en 1955[1].

Définition formelle[modifier | modifier le code]

Une machine de Mealy est constituée des données suivantes :

  • un ensemble fini d'états Q ;
  • un état initial i, élément de Q ;
  • un ensemble fini A, appelé alphabet d'entrée ;
  • un ensemble fini B, appelé alphabet de sortie ;
  • une fonction de transition \delta : Q\times A\to Q;
  • une fonction de sortie \lambda : Q\times A\to B.

Il est commode de noter l'état \delta(q,a) par q\cdot a et le symbole de sortie \lambda(q,a) par q\star a. La fonction de transition et la fonction de sortie sont étendues aux mot de A^* par récurrence, pour w\in A^* et a\in A, par

q\cdot wa = (q\cdot w)\cdot a,\quad q\star wa =(q\star w)((q\cdot w)\star a).

En d'autre termes, la sortie produite par le mot wa, lu à partir de l'état q, est le mot produit par le mot w, lu à partir de l'état q, suivi de la lettre produite par le symbole a, lu à partir de l'état q\cdot w atteint après la lecture de w.

La fonction réalisée par l’automate de Mealy est l'application f: A^*\to B^* définie par:

f(w)=i\star w

C'est donc la fonction qui à un mot w de A^*, lu à partir de l'état initial i, associe le mot sur B^* obtenu en concaténant les lettres de sortie des transitions parcourues.

Variante[modifier | modifier le code]

Parfois, une machine de Mealy est dotée d'un ensemble fini d'état terminaux. La fonction f réalisée est alors restreinte aux mot du langage rationnel sur l'alphabet d'entrée reconnu par l'automate. Le langage des mots produits par la fonction f est alors un langage rationnel.

Exemples[modifier | modifier le code]

Décalage[modifier | modifier le code]

Dans l'exemple ci-dessus, le mot produit par la lecture d'un mot w à partir de l'état initial S_0 consiste à préfixer w par la lettre 0, puis à recopier w, à l'exception de sa dernière lettre. Par exemple

f(000110011)=000011001,\quad f(100110011)=010011001.

Le résultat est donc le décalage de l’entrée d'un chiffre, avec perte du dernier symbole.

« Ou » exclusif (addition modulo 2)[modifier | modifier le code]

Une machine de Mealy pour le « ou » exclusif.

L'automate ci-contre réalise le « ou » exclusif ou addition modulo 2 des deux chiffres binaires consécutifs de l'entrée, avec recopie du premier symbole. Cette propriété est utilisée par exemple dans la détection de contour. Les entrées sont représentées en rouge, les sorties en bleu. Soit f la fonction réalisée. On obtient par exemple

f(000110011)=00010100,\quad f(100110011)=010101010.

Applications[modifier | modifier le code]

Les machines de Mealy fournissent un modèle mathématique rudimentaire pour représenter le chiffrement des informations. Supposons que l'alphabet d'entrée et l'alphabet de sortie soient l'ensemble des chaînes de caractères latins. Il est possible de concevoir une machine de Mealy transformant une chaîne de caractères en clair (entrée) en une chaîne chiffrée (sortie). Cet exemple est toutefois théorique, car s'il est possible de décrire Enigma (par exemple) en utilisant une machine de Mealy, le diagramme états-transitions en serait trop complexe pour une interprétation efficace.

Transformation d'une machine de Mealy en machine de Moore[modifier | modifier le code]

Pour transformer une machine de Mealy en machine de Moore, on peut procéder en trois étapes comme suit:

  • Étape 1: Dupliquer les états et détourner les transitions entrantes.
    Chaque état est dupliqué en autant d'exemplaires qu'il y a de symboles de sorties sur les transitions entrant dans cet état. Les transitions entrantes sont détournées, de sorte que les transitions entrantes dans un état on toutes même symbole de sortie.
  • Étape 2: Écrire les sorties dans les états.
    Pour chaque transition, on reporte le symbole de sortie dans l'état d'arrivée. Grâce à la duplication préalable des états, il y a un seul symbole de sortie associée à un état.
  • Étape 3: Dupliquer les transitions sortantes.
    Les transitions sortantes d'un état sont dupliquées sur chaque copie d'état réalisée à l'étape 1.

L'automate obtenu est un automate de Moore équivalent à l'automate de Mealy de départ. Son nombre d'états est au plus \left|Q\right|\cdot\left|B\right|, où Q est l'ensemble d'états de l'automate de Mealy, et B est l'alphabet de sortie.

Cliquez sur une vignette pour l’agrandir

Voir aussi[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. Mealy, G.H. "A Method for Synthesizing Sequential Circuits". Bell System Tech. J. 34 (1955): 1045–1079.