Machine de Mealy

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.

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.

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.

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.

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

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