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. Cet automate tient son nom de George H. Mealy, qui a proposé ce modèle en 1955. Ils font maintenant partie des concepts de base en théorie des automates et des langages rationnels et figurent dans de nombreux manuels 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. Une machine de Mealy est constituée des données suivantes : 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'autres 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 produite par le symbole lu à partir de l'état atteint après la lecture de . La fonction réalisée par l’automate de Mealy 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 de sortie des transitions parcourues.

À 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.
Cours associés (7)
EE-381: Electronics III
Comparaison entre les systèmes à composants discrets et les systèmes intégrés. Introduction aux systèmes électroniques numériques et analogiques et à leur interfaçage. Analyse sous forme d'un projet
EE-110: Logic systems (for MT)
Ce cours couvre les fondements des systèmes numériques. Sur la base d'algèbre Booléenne et de circuitscombinatoires et séquentiels incluant les machines d'états finis, les methodes d'analyse et de syn
COM-302: Principles of digital communications
This course is on the foundations of digital communication. The focus is on the transmission problem (rather than being on source coding).
Afficher plus
Séances de cours associées (38)
Conceptions logiques séquentielles
Introduit des systèmes cadencés, des circuits séquentiels, des dispositifs à états bistables, des états métastables et des bascules de type D.
Systèmes logiques : Machines à états finis
Explore l'algèbre booléenne, l'optimisation, les systèmes séquentiels et la conception de machines à états finis.
Les machines à états finis : Medvedev vs. Moore vs. Mealy
Comparaison des modèles Medvedev, Moore et Mealy FSM et de leurs structures.
Afficher plus
Publications associées (30)

Machine Learning Methods for Robust Uncertainty Quantification and Controller Approximation

Emilio Maddalena

This thesis is situated at the crossroads between machine learning and control engineering. Our contributions are both theoretical, through proposing a new uncertainty quantification methodology in a kernelized context; and experimental, through investigat ...
EPFL2023

Investigating the neuromechanical control of healthy gait modulation and pathological gaits observed in cerebral palsy using neuromuscular simulations

Andrea Di Russo

Locomotion is based on a sophisticated interaction among the environment, the musculoskeletal system, the spinal cord, and the brain locomotor areas. Quality of life is strongly related to the proper capability of this movement. However, many pathologies, ...
EPFL2023

Review of control strategies for lower-limb exoskeletons to assist gait

Auke Ijspeert, Mohamed Bouri, Ali Reza Manzoori, Romain Pierre François Baud

Background Many lower-limb exoskeletons have been developed to assist gait, exhibiting a large range of control methods. The goal of this paper is to review and classify these control strategies, that determine how these devices interact with the user. Met ...
BMC2021
Afficher plus
Concepts associés (6)
Machine de Moore
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.
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.
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.
Afficher plus

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.