Machine de Moore

Cet article est une ébauche concernant l’informatique théorique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Le diagramme états-transitions d'une machine de Moore avec une fonction de transition partielle. Les entrées sont x, y, z, et les sorties a, b, c.

En informatique théorique, notamment en théorie des automates, et en théorie de la calculabilité, une machine de Moore ou automate de Moore (proposée par Edward F. Moore) est un transducteur fini (i.e. un automate fini avec une sortie) pour lequel les sorties ne dépendent que de l'état courant. Cela signifie que chaque état est doté d'une lettre de sortie. La lettre est émise lorsque l'état est atteint. En particulier, la longueur du mot de sortie est égale à la longueur du mot d'entrée.

Cette définition est plus restrictive que celle des machines de Mealy pour lesquelles les valeurs de sortie dépendent à la fois de l'état courant et de la lettre d'entrée. Toutefois, il existe pour chaque machine de Moore, une machine de Mealy équivalente et réciproquement.

Les machines de Moore constituent la famille la plus simple de transducteurs finis.

Définition formelle[modifier | modifier le code]

Une machine de Moore est un 6-uplet

(Q,i,A,B,\delta ,\lambda )

constitué de :

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

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

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 $wa$ , lu à partir de l'état $q$ , est le mot produit par le mot $w$ , lu à partir de l'état $q$ , suivi de la lettre associée à l'état $q\cdot wa$ atteint après la lecture de $wa$ .

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

f(w)=i\star w

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

Variantes[modifier | modifier le code]

Parfois, une machine de Moore est dotée d'un ensemble fini d'état terminaux. La fonction $f$ réalisée est alors restreinte aux mot du langage rationnel sur l'alphabet d'entrée reconnu par l'automate. Le langage des mots produits par la fonction $f$ est alors un langage rationnel.

Usuellement, la fonction de transition $\delta :Q\times A\to Q$ est totale; lorsqu'elle est partielle, l'absence d'une transition a pour conséquence le blocage de l'automate.

Exemple[modifier | modifier le code]

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

Transformation en automate de Mealy[modifier | modifier le code]

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 :

Un problème[modifier | modifier le code]

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 :

Théorème 8 — Étant donné une machine de type (n ; m ; p) telle que deux quelconques de ses états sont distinguables, il existe une expérience de longueur $n(n-1)/2$ qui détermine l'état à la fin de l'expérience.

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 :

Théorème — Étant donné une machine de type (n ; m ; p) telle que deux quelconques de ses états sont distinguables, il existe une expérience de longueur $(n-1)(n-2)/2+1$ qui détermine l'état à la fin de l'expérience. De plus, cette borne est atteinte.

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

Notes[modifier | modifier le code]

↑ (en) A. A. Karatsuba, « Solution of one problem from the theory of finite automata », Usp. Mat. Nauk, n^o 15:3,‎ 1960, p. 157–159.

(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).

Voir aussi[modifier | modifier le code]

[1] (en) A. A. Karatsuba, « Solution of one problem from the theory of finite automata », Usp. Mat. Nauk, n^o 15:3,‎ 1960, p. 157–159.

[1]

v · m Automates finis et langages réguliers
Articles généraux	Théorie des automates Automate fini Machine abstraite
Automates finis	Automate fini déterministe Automate fini inambigu Automate fini non déterministe Construction par sous-ensembles Automate sur les mots infinis
Automates finis particuliers	Automate alternant Automate bidirectionnel Automate pondéré Automate probabiliste Automate quantique Automate temporisé Automate de Büchi Automate de Muller Modèle de Markov caché Système de transition d'états Structure de Kripke Machine à états abstraits Machine de Mealy Machine de Moore Transducteur fini Automate séquentiel
Langages réguliers	Langage rationnel Langage sans étoile Langage local Langage congruentiel Langage stochastique Lemme de l'étoile Lemme d'Arden ω-langage rationnel
Des automates aux langages	Expression régulière Algorithme de Conway Algorithme de McNaughton et Yamada Méthode de Brzozowski et McCluskey
Des langages aux automates	Dérivée de Brzozowski Algorithme de Thompson Construction de Glushkov Complexité en états
Minimisation	Théorème de Myhill-Nerode Équivalence de Nerode Minimisation d'un automate fini déterministe Algorithme de Moore Algorithme de Brzozowski Algorithme de Hopcroft
Équivalences	Théorème de Kleene Étoile de Kleene Monoïde syntaxique Théorème des variétés d'Eilenberg