Machine de Mealy

Un article de Wikipédia, l'encyclopédie libre.

Cet article est une ébauche concernant l’informatique.

Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

Le diagramme états-transitions d'une machine de Mealy simplifiée.

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 à état fini) pour lequel les valeurs des variables de sortie dépendent à la fois de l'état courant et des variables d'entrée. Cela signifie que le diagramme états-transitions inclura à la fois un signal d'entrée et un signal de sortie pour chaque transition. Cette définition s'oppose à celle des machines de Moore pour lesquelles les valeurs en sortie ne dépendent que de l'état courant. Cependant, il existe pour chaque machine de Mealy, une machine de Moore équivalente.

Cet automate tient son nom de G. H. Mealy, qui proposa ce modèle en 1955^[1].

[modifier] Définition formelle

Une machine de Mealy est un 6-uplet, (S, S₀, Σ, Λ, T, G), constitué de :

un nombre fini d'états S ;
un état initial S₀, où S₀ $\in$ S ;
un ensemble fini Σ, appellé alphabet d'entrée ;
un ensemble fini Λ, appellé alphabet de sortie ;
une fonction de transition T : S × Σ → S ;
une fonction de sortie G : S × Σ → Λ.

[modifier] Applications

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.