Copyright HébergementWebs.com - License GPL

Machines Moore et Mealy

Tutoriel sur la théorie des automates   2021-01-04 11:43:15

Machines Moore et Mealy Les automates finis peuvent avoir des sorties correspondant à chaque transition. Il existe deux types de machines à états finis qui génèrent une sortie - Mealy Machine Moore machine Machine Mealy Une Machine Mealy est un FSM dont la sortie dépend de l"état actuel ainsi que de l"entrée actuelle. Elle peut être décrite par un 6 tuple (Q, ∑, O, δ, X, q 0 ) où - Q est un ensemble fini d"états. ∑ est un ensemble fini de symboles appelé alphabet d"entrée. O est un ensemble fini de symboles appelé alphabet de sortie. δ est la fonction de transition d"entrée où δ: Q × ∑ → Q X est la fonction de transition de sortie où X: Q × ∑ → O q0 est l"état initial à partir duquel toute entrée est traitée (q 0 ∈ Q). La table d"état d"une machine Mealy est présentée ci-dessous - État actuel État suivant input = 0 input = 1 État Sortie État Sortie → a b x 1 c x 1 b b x 2 d x 3 c d x 3 c x 1 d dx3dx2 Le diagramme d"état de la machine Mealy ci-dessus est - Machine Moore Machine Moore est un FSM dont les sorties ne dépendent que de l"état actuel. Une machine de Moore peut être décrite par un 6 tuple (Q, ∑, O, δ, X, q 0 ) où - Q est un ensemble fini d"états. ∑ est un ensemble fini de symboles appelé alphabet d"entrée. O est un ensemble fini de symboles appelé le l"alphabet de sortie. δ est la fonction de transition d"entrée où δ: Q × ∑ → Q X est la fonction de transition de sortie où X: Q → O q 0 est l"état initial à partir duquel toute entrée est traitée (q 0 ∈ Q). La table d"état d"une machine Moore est présentée ci-dessous - État actuel État suivant Sortie Input = 0 Entrée = 1 → a b c x 2bbd x 1 c c d x 2 d d d x 3 Le diagramme d"état de la machine Moore ci-dessus est - Mealy Machine vs. Moore Machine Le tableau suivant met en évidence les points qui différencient un Mealy Machine à partir d"une machine Moore. Mealy Machine Moore Machine La sortie dépend à la fois de l"état actuel et de l"entrée actuelle La sortie dépend uniquement de l"état actuel. Généralement, il a moins d"états que Moore Machine. En général, il a plus d"états que Mealy Machine. La valeur de la fonction de sortie est une fonction des transitions et des changements, lorsque la logique d"entrée sur l"état présent est effectuée. La valeur de la fonction de sortie est fonction de l"état actuel et des changements aux fronts d"horloge, chaque fois que des changements d"état se produisent . Les machines farineuses réagissent plus rapidement aux entrées. Ils réagissent généralement dans le même cycle d"horloge. Dans les machines Moore, plus de logique est nécessaire pour décoder les sorties, ce qui entraîne plus de retards de circuit. Ils réagissent généralement un cycle d"horloge plus tard. Moore Machine to Mealy Machine Algorithme 4 Entrée - Moore Machine Sortie - Mealy Machine Étape 1 - Prenez un format de table de transition Mealy Machine vierge. Étape 2 - Copiez tous les états de transition de Moore Machine dans ce format de tableau. Étape 3 - Vérifiez les états actuels et leurs sorties correspondantes dans la table d"état de Moore Machine; si pour un état Q i la sortie est m, copiez-la dans les colonnes de sortie de la table d"état de la machine Mealy partout où Q i apparaît dans l"état suivant. Exemple Considérons la machine de Moore suivante - État actuel État suivant Sortie a = 0 a = 1 → a d b 1 b a d 0 c c c 0 dba1 Nous appliquons maintenant l"algorithme 4 pour le convertir en Mealy Machine. Étape 1 & 2 - État actuel État suivant a = 0 a = 1 État Sortie État Sortie → a d bba d c c c d b a Étape 3 - État actuel État suivant a = 0 a = 1 État Sortie État Sortie => a d 1 b0ba 1 d 1 c c 0 c 0 d b 0 a 1 Machine farineuse vers machine Moore Algorithme 5 Entrée - Machine farineuse Sortie - Machine Moore Étape 1 - Calculer le nombre de sorties différentes pour chaque état (Q i ) qui sont disponibles dans la table d"état de la machine Mealy. Étape 2 - Si toutes les sorties de Qi sont identiques, copiez l"état Q i . S"il a n sorties distinctes, i en n états comme Q in où n = 0, 1, 2 ..... .. Étape 3 - Si la sortie de l"état initial est 1, insérez un nouvel état initial au début qui donne 0 sortie. Exemple Considérons la machine Mealy suivante - État actuel État suivant a = 0 a = 1 État suivant Sortie État suivant Sortie → a d 0 b 1 b a 1 d 0 c c 1 c 0 d b 0 a 1 Ici, les états "a" et "d" ne donnent respectivement que 1 et 0 sorties, donc on retient les états «a» et «d». Mais les états «b» et «c» produisent des sorties différentes (1 et 0). Donc, nous b en b 0 , b 1 et c en c 0 , c 1 . État actuel État suivant Sortie a = 0 a = 1 → a d b 1 1 b 0 a d 0 b1ad 1 c 0 c 1 C 0 0 c 1 c 1 C 0 1 d b 0 a0