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 transducteur fini (i.e. un automate fini avec une sortie) 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. Ils font maintenant partie des concepts de base en théorie des automates et des langages rationnels et figurent dans de nombreux manuels Les automates de Mealy ont des applications en théorie géométrique des groupes, où ils interviennent, depuis les travaux de Rostislav Grigorchuk, dans la définition de groupes d'automorphismes à croissance intermédiaire. Une machine de Mealy est constituée des données suivantes : un ensemble fini d'états ; un état initial , élément de ; un ensemble fini , appelé alphabet d'entrée ; un ensemble fini , appelé alphabet de sortie ; une fonction de transition ; une fonction de sortie . Il est commode de noter l'état par et le symbole de sortie par . La fonction de transition et la fonction de sortie sont étendues aux mots de par récurrence, pour et , par En d'autres termes, la sortie produite par le mot lu à partir de l'état est le mot produit par le mot lu à partir de l'état , suivi de la lettre produite par le symbole lu à partir de l'état atteint après la lecture de . La fonction réalisée par l’automate de Mealy est l'application définie par: C'est donc la fonction qui, à un mot de lu à partir de l'état initial , associe le mot sur obtenu en concaténant les lettres de sortie des transitions parcourues.