Machine de Moore

Une machine de Moore est un 6-uplet

${\displaystyle (Q,i,A,B,\delta ,\lambda )}$

constitué de :

• 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\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\cdot 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'autre 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 associée à l'état ${\displaystyle q\cdot wa}$ atteint après la lecture de ${\displaystyle wa}$.

La fonction réalisée par l’automate de Moore 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 associés aux états d'arrivée des transitions parcourues.

L'exemple ci-dessus a quatre états. La fonction de transition est partiellement définie sur l'état En prenant ${\displaystyle q_{0}}$ comme état initial, l'automate produit, pour le mot d'entrée ${\displaystyle zxzy}$, le mot de sortie ${\displaystyle acac}$. La lettre ${\displaystyle b}$ n'est jamais produite parce qu'il n'y a pas de transition aboutissant en ${\displaystyle q_{0}}$.

La transformation d'un automate de Moore en automate de Mealy équivalent est très simple. On ajoute à une transition la lettre de sortie de l'état d'arrivée. Sur l'exemple, le résultat est le suivant :

Transformation d'une machine de Moore en machine de Mealy.

Dans son article cité en référence, Moore considère des machines de type (n ; m ; p). Ce sont des automates ayant n états, m symboles d'entrée et p symboles de sortie. Dans la section Further problems à la fin de son article, il suggère d'étudier le problème suivant : « Améliorer les bornes données dans les théorèmes 8 et 9 ». Le théorème 8 est le suivant :

Anatolii Alexevich Karatsuba a résolu ce problème de Moore consistant à améliorer la borne ci-dessus, en prouvant, en 1957, alors qu'il était étudiant à la faculté de mécanique de l'université d'État Lomonossov de Moscou, le résultat suivant :

Ce résultat a été publié en 1960[1].

• (en) Edward F. Moore, « Gedanken-experiments on sequential machines », dans C. Shannon et J. McCarthy (éditeurs), Automata studies, Princeton, N. J., Princeton University Press, coll. « Annals of mathematics studies » (n^o 34), 1956, p. 129--153

• (en)/(de) Cet article est partiellement ou en totalité issu des articles intitulés en anglais « Moore machine » (voir la liste des auteurs) et en allemand « Moore-Automat » (voir la liste des auteurs).

• Automate fini
• Machine de Mealy
• Transducteur fini