Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Machine de Moore
Résumé
thumb|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.
Une machine de Moore est un 6-uplet
constitué de :
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'autre 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 associée à l'état atteint après la lecture de .
La fonction réalisée par l’automate de Moore 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 associés aux états d'arrivée des transitions parcourues.
Parfois, une machine de Moore est dotée d'un ensemble fini d'état terminaux. La fonction réalisée est alors restreinte aux mot du langage rationnel sur l'alphabet d'entrée reconnu par l'automate.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Proximité ontologique
Publications associées (21)
Concepts associés (5)
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.
Table de transition d'état
Dans la théorie des automates et en logique séquentielle, une table de transition d'état est un tableau montrant dans quel état (ou états dans le cas d'un automate fini non déterministe) d'un automate fini se déplacer, sur la base de l'état actuel et des autres entrées. Une table d'état est essentiellement une table de vérité, dans laquelle certaines des entrées sont l'état actuel, et les sorties comprennent l'état suivant, en même temps que les autres sorties.
Diagramme états-transitions
Un diagramme états-transitions est un schéma utilisé en génie logiciel pour représenter des automates déterministes. Il fait partie du modèle UML et s'inspire principalement du formalisme des statecharts et rappelle les grafcets des automates. S'ils ne permettent pas de comprendre globalement le fonctionnement du système, ils sont directement transposables en algorithme. En effet, contrairement au diagramme d'activité qui aborde le système d'un point de vue global, le diagramme états-transitions cible un objet unique du système.