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.

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

Cet automate tient son nom de George H. Mealy, qui a proposé ce modèle en 1955^[1]. Ils font maintenant partie des concepts de base en théorie des automates et des langages rationnels et figurent dans de nombreux manuels^{[2],[3],[4], [5]}.

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.

Définition formelle

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

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

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

${\displaystyle q\cdot wa=(q\cdot w)\cdot a,\quad q\star wa=(q\star w)((q\cdot w)\star a).}$

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

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

${\displaystyle f(w)=i\star w}$

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

Variante

Parfois, une machine de Mealy est dotée d'un ensemble fini d'état terminaux. La fonction ${\displaystyle f}$ réalisée est alors restreinte aux mots du langage rationnel sur l'alphabet d'entrée reconnu par l'automate.

Exemples

Décalage

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

${\displaystyle 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)

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 ${\displaystyle f}$ la fonction réalisée. On obtient par exemple

${\displaystyle f(000110011)=000101010,\quad f(100110011)=010101010.}$

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 constituées de 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 : par exemple, s'il est possible de décrire la machine de chiffrement Enigma en utilisant une machine de Mealy, le diagramme états-transitions reste trop complexe pour une interprétation efficace.

Transformation d'une machine de Mealy en machine de Moore

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 manière que lorsqu'elles entrent dans un état, elles aient toutes le 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é à 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 ${\displaystyle \left|Q\right|\cdot \left|B\right|}$, où ${\displaystyle Q}$ est l'ensemble d'états de l'automate de Mealy, et ${\displaystyle B}$ est l'alphabet de sortie.

• 
  Automate de départ.
• 
  Étape 1. Duplication des états.
• 
  Étape 2. Écriture des sorties dans les états.
• 
  Étape 3. Duplication des transitions sortantes.

Automates de Mealy et demi-groupes à croissance intermédiaire

Automate de Grigorchuk.

Les automates de Mealy sont des modèles utilisés en théorie des groupes pour décrire des groupes ou des demi-groupes de transformations. Ils se prêtent notamment à la construction de groupes et demi-groupes à croissance dite « intermédiaire », ni polynomiale ni exponentielle. Les premiers groupes ont été mis en évidence par Rostislav Grigorchuk (le groupe de Grigorchuk). Le plus petit automate qui donne un demi-groupe à croissance intermédiaire est décrit en détail par Bartholdi et al.^[6] et est appelé l'« automate de Sushchanskii » par Bartholdi ^[7].

Automate de Sushchanskiĭ

Les automates de Mealy inversibles à deux états et sur deux lettres, qui donnent des groupes de transformations, ont été tous décrits, par R. I. Grigorchuk, V. V. Nekrashevich et V. I. Sushchanskiĭ^[8]. Les demi-groupes de transformation deux lettres définis par des automates de Mealy sur deux états sont aussi connus^[6]. Parmi eux, il y a l'automate de Sushchanskiĭ qui a la particularité que son taux de croissance, intermédiaire, est connu ; il est

${\displaystyle \gamma (n)\sim 2^{5/2}3^{3/4}\pi ^{-2}n^{1/4}\exp(\pi {\sqrt {n/6}})}$

Les automates considérés sont des automates Mealy particuliers : ils ont même alphabet d'entrée et de sortie, en général ${\displaystyle \{0,1\}}$, et n'ont pas d'états initiaux ni terminaux. Les états sont en bijection avec les générateurs du groupe ou demi-groupe, augmentés de l'automorphisme identité. Les transitions sont les quadruplets ${\displaystyle (p,i,j,q)}$ tels que ${\displaystyle p(ix)=jq(x)}$ dans le demi-groupe, où ${\displaystyle i,j\in \{0,1\}}$ et ${\displaystyle p,q}$ sont des généraleurs du demi-groupe ou l'identité. On voit qu'il existe un chemin de ${\displaystyle p}$ à ${\displaystyle q}$ d'étiquette d'entrée ${\displaystyle y}$ et d'étiquette de sortie ${\displaystyle z}$, soit ${\displaystyle p\cdot y=q}$ et ${\displaystyle p*y=z}$ si et seulement si ${\displaystyle p(yx)=zq(x)}$. Par exemple, il y a dans l’automate de Grigorchuk un chemin

${\displaystyle b\,{\xrightarrow {1|1}}\,c\,{\xrightarrow {0|0}}\,a\,{\xrightarrow {1|0}}\,e\,{\xrightarrow {1|1}}\,e}$

représentant le calcul

${\displaystyle b(1011)=1c(011)=10a(11)=1001}$.

L'étude des automates de Mealy et des groupes et demi-groupes de transformations qu'ils définissent a été poursuivie par Thibault Godin, Inès Klimann, Matthieu Picantin^[9].

Formellement, tout état ${\displaystyle p}$ réalise une fonction ${\displaystyle \rho _{p}:\{0,1\}^{*}\to \{0,1\}^{*}}$, notée aussi ${\displaystyle p}$ quand il n'y a pas de confusion possible, vérifiant ${\displaystyle \rho _{p}(x)=p*x}$ et appelée transformation automatique associée à ${\displaystyle p}$. Les fonctions réalisées peuvent être composées : si ${\displaystyle \rho _{q}:\{0,1\}^{*}\to \{0,1\}^{*}}$ est associée à l’état ${\displaystyle q}$, alors ${\displaystyle \rho _{q}\circ \rho _{p}(x)=q*(p*x)}$, en d'autres termes la sortie de la fonction associée à ${\displaystyle p}$ devient l’entrée de la fonction associée à ${\displaystyle q}$. Les mots ${\displaystyle x,p*x}$ et ${\displaystyle q*p*x}$ ont même longueur. Plus généralement, on associe à tout mot ${\displaystyle w}$, produit de générateurs du demi-groupe, une fonction ${\displaystyle f_{w}}$ définie par composition des fonctions des générateurs.

Le taux de croissance ${\displaystyle \gamma (n)}$ est le nombre d'éléments distincts du demi-groupe qui produit de ${\displaystyle n}$ générateurs sans être produit de moins de générateurs.

Les demi-groupes à deux états et à deux symboles se répartissent en deux demi-groupes finis, sept demi-groupes à croissances polynomiale, un à croissance intermédiaire (l'automate de Sushchanskii), et huit demi-groupes à croissance exponentielle, y compris le demi-groupe libre^[7].

Plusieurs types d'automates de Mealy existent : un automate est inversible si les étiquettes de sortie des transitions d'un état sont toutes distinctes. Alors chaque état définit une permutation sur les étiquettes de sortes. L'automate de Grigorchuk est inversible, l'automate de Sushchanskii ne l’est pas puisque les deux transitions de l’état ${\displaystyle ront}$ le même symbole de sortie. Le demi-groupe engendré par un automate inversible est un groupe. Le dual d'un automate est l'automate obtenu en échangeant les états et les lettres : formellement, chaque transition ${\displaystyle (p,i,j,q)}$ donne une transition ${\displaystyle (i,p,q,j)}$ du dual. Un automate est réversible quand les fonctions de transitions de l’automate sont des permutations de l’ensemble des états ou, de manière équivalente, quand son dual est inversible^[10]. Un exemple d'automate inversible est l'automate dit du groupe de l’allumeur de réverbères, en anglais « lamplighter group »^[11],[12]. Comme il s'agit d'automates inversibles sur deux lettres, les transitions sortant d'un état sont soit ${\displaystyle 0|0}$ et ${\displaystyle 1|1}$, soit ${\displaystyle 0|1}$ et ${\displaystyle 1|0}$. Une écriture remontant aux premiers travaux de Grigorchuk et toujours utilisée consiste à étiqueter un état par 1 ou par ε selon qu'il est de la première ou de la deuxième espèce, et de ne pas indique explicitement la sortie sur les transitions ; ainsi, une transition ${\displaystyle (p,0,1,q)}$ est remplacée par ${\displaystyle (p_{\epsilon },0,q)}$. Une autre famille est constituée des automates biréversibles^[13].

• Automates du groupe de l'allumeur de réverbères
• 
  Automate de l'allumeur de réverbères.
• 
  Inverse de l'automate.
• 
  Dual de l'automate.
• 
  Variante de représentation.

Notes et références

1. George H. Mealy, « A Method for Synthesizing Sequential Circuits », Bell System Tech. J. 34 (1955) : 1 045–1 079.
2. (en) W.M.L. Holcombe, Algebraic automata theory, vol. 1, Cambridge University Press, coll. « Cambridge Studies in Advanced Mathematics », 1982 (ISBN 0-521-60492-3, zbMATH 0489.68046)
3. Jean-Eric Pin, chap. I/9 « Algorithmique et Programmation. Automates finis », dans Jacky Akoka et Isabelle Comyn-Wattiau (éditeurs), Encyclopédie de l’informatique et des systèmes d’information, Paris, Vuibert, 2006 (ISBN 978-2711748464, lire en ligne), p. 966-976
4. Jean-Éric Pin, « Petit cours sur les fonctions séquentielles », Sainte-Marie de Ré, sur www.irif.fr, LIAFA, CNRS et Université Denis Diderot, mai 2013, (consulté le 3 août 2017).
5. Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, 2003, 816 p. (ISBN 978-2-7117-4807-5). — Traduction anglaise (par Reuben Thomas) : Elements of Automata Theory, Cambridge University Press 2009, (ISBN 9780521844253).
6. (en) Laurent Bartholdi, Ilya I. Reznykov et Vitalii I. Sushchansky, « The smallest Mealy automaton of intermediate growth », Journal of Algebra, vol. 295, n^o 2,‎ 2006, p. 387–414 (ISSN 0021-8693, DOI 10.1016/j.jalgebra.2004.08.040, arXiv math/0407312v1, lire en ligne).
7. Laurent Bartholdi, « Decidability problems in automaton semigroups », preprint,‎ 2017 (arXiv 1705.04598v1).
8. R.I. Grigorchuk, V.V. Nekrashevich et V.I. Sushchanskiĭ, « Automata, dynamical systems, and groups », Proc. Steklov Inst. Math., vol. 231,‎ 2000, p. 128–203 (MR 1841755).
9. Thibault Godin, Ines Klimann et Matthieu Picantin, « On torsion-free semigroups generated by invertible reversible Mealy automata », LATA 2015, Springer,‎ 2015, p. 328–339 (DOI 10.1007/978-3-319-15579-1_25, MR 3344813, arXiv abs/1410.4488).
10. Thibault Godin, Machines de Mealy, (semi-)groupes d’automate, problèmes de décision et génération aléatoire, thèse de doctorat, Université Paris Diderot, 2017 (lire en ligne).
11. (en) Rostislav I. Grigorchuk et Andrzej Żuk, « The lamplighter group as a group generated by a 2-state automaton, and its spectrum », Geometriae Dedicata, vol. 87, n^os 1-3,‎ 2001, p. 209–244 (ISSN 0046-5755, DOI 10.1023/A:1012061801279).
12. (en) Ali Akhavi, Ines Klimann, Sylvain Lombardy, Jean Mairesse et Matthieu Picantin, « On the finiteness problem for automaton (semi)groups », Int. J. Algebra Comput., vol. 22, n^o 6,‎ 2012, p. 1–26 (zbMATH 1280.20038, arXiv 1105.4725).
13. (en) Thibault Godin et Ines Klimann, « On bireversible Mealy automata and the Burnside problem », Theoretical Computer Science, vol. 707,‎ 2018, p. 24–35 (DOI 10.1016/j.tcs.2017.10.005).

Voir aussi

• Automate fini
• Machine de Moore
• Transducteur fini
• Transduction rationnelle
• Groupe de Grigorchuk

• Portail de la logique
• Portail de l'informatique théorique