Table de transition d'état

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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.

Une table d'état est l'un des moyens de spécifier un Automate fini, d'autres moyens étant un Diagramme états-transitions, et une équation caractéristique.

Les formes communes[modifier | modifier le code]

Tables d'état à une dimension[modifier | modifier le code]

Aussi appelées tableaux caractéristiques, les tables d'état à une dimension ressemblent beaucoup plus à des tables de vérité que les versions en deux dimensions. Les entrées sont généralement placées sur la gauche, et séparées des sorties, qui sont sur la droite. Les sorties représentent l'état suivant de la machine.

Voici un exemple simple d'une machine d'état avec deux états et deux entrées combinatoires:

A B État actuel État suivant Sortie
0 0 S1 S2 1
0 0 S2 S1 0
0 1 S1 S2 0
0 1 S2 S2 1
1 0 S1 S1 1
1 0 S2 S1 1
1 1 S1 S1 1
1 1 S2 S2 0

S1 et S2 représentent très probablement les bits 0 et 1 simple, car un seul bit ne peut avoir que deux états.

Tables d'état à deux dimensions[modifier | modifier le code]

Les tables de transition d'état sont généralement des tables à deux dimensions. Il existe deux formes communes pour les arranger.

  • L'axe vertical (ou horizontal) indique les états actuels, l'axe horizontal (ou vertical) indique des événements, et les cellules (intersections ligne / colonne) dans la table contiennent l'état suivant si un événement se produit (et éventuellement l'action liée à cette transition d'état).
Table de transition d'état
  Événement
État
E1 E2   ...   En
S1 - Ay/Sj ... -
S2 - - ... Ax/Si
... ... ... ... ...
Sm Az/Sk - ... -

(S: État, E: Événement, A: action, -: passage illégal)

  • L'axe vertical (ou horizontal) indique les états actuels, l'axe horizontal (ou vertical) indique états suivants, et les intersections de lignes / colonnes contiennent l'événement qui va conduire à un état particulier prochain.
Table de transition d'état
      suivant
actuel
S1 S2   ...   Sm
S1 - - ... Ax/Ei
S2 Ay/Ej - ... -
... ... ... ... ...
Sm - Az/Ek ... -

(S: État, E: Événement, A: action, -: transition impossible)

D'autres formes[modifier | modifier le code]

Des transitions simultanées dans plusieurs machines à états finis peuvent être montrées dans ce qui est effectivement un tableau de transition d'états à n dimensions dans lequel des paires de lignes font correspondre des (ensembles d') états actuels avec les états suivants[1]. Il s'agit d'une alternative à la représentation de la communication entre des machines à états interdépendants

À l'autre extrême, des tableaux distincts ont été utilisés pour chacune des transitions dans un machine d'état seule : les tableaux "AND/OR"[2] sont similaires à des tables de décision incomplètes dans lesquelles la décision relative aux règles présentes est implicitement l'activation de la transition associée.

Exemple[modifier | modifier le code]

Un exemple d'une table de transition d'état pour une machine ‘’‘M’‘’ avec le diagramme d'état correspondant est donné ci-dessous.

Table de transition d'état
  Entrées
État
1 0
S1 S1 S2
S2 S2 S1
  Diagramme de transition d'état
DFAexample.svg

Toutes les entrées possibles de la machine sont énumérées dans les colonnes de la table. Tous les états possibles sont énumérés dans les rangées. Avec la table de transition d'état ci-dessus, il est facile de voir que si la machine est dans l'état S1 (la première ligne), et l'entrée suivante est 1, la machine restera dans l'état S1. Un 0 permet à la machine d'entamer une transition vers l'état S2 comme indiqué dans la deuxième colonne. C'est ce qui est représenté dans le diagramme par la flèche allant de S1 à S2 marquée par un 0.

Dans le cas d'un automate fini non déterministe (NFA), une nouvelle entrée peut mettre la machine dans de multiples états, d'où son nom de non-déterministe. Ceci est indiqué dans un tableau de transition d'état par une paire d'accolades { } avec l'ensemble des états cibles à l'intérieur.

Un exemple est donné ci-dessous.

Table de transition d'état pour un NFA
  Entrées
état
1 0 ε
S1 S1 { S2, S3 } Φ
S2 S2 S1 Φ
S3 S2 S1 S1

Ici, une machine non déterministe dans l'état S1 qui lit une entrée de 0, sera dans deux états en même temps, les États S2 et S3. La dernière colonne définit la transition juridique des États de la spécificité, ε. Ce caractère spécial permet à la machine de passer à un état différent alors qu'elle ne reçoit aucune entrée. Dans l'état S3, la NFA peut se déplacer à S1 sans consommer un caractère d'entrée. Les deux cas ci-dessus font de l'automate décrit un automate fini non déterministe.

Transformations à partir et vers un diagramme d'état[modifier | modifier le code]

Il est possible de dessiner un diagramme d'état à partir de la table. Une séquence d'étapes faciles à suivre est donnée ci-dessous:

  1. Dessinez des cercles pour représenter les états donnés.
  2. Pour chacun des états, balayer la ligne correspondante et tirer une flèche vers l'état ou les états de destination. Il peut y avoir plusieurs flèches pour un caractère d'entrée si l'automate est non-déterministe.
  3. Désigner un état comme l'état de départ. L'état initial est donné dans la définition formelle de l'automate.
  4. Désigner un ou plusieurs états comme états finaux. Ceci est également donné dans la définition formelle.

Voir aussi[modifier | modifier le code]

Excitation table

Bibliographie[modifier | modifier le code]

  1. Breen, Michael (2005), "Experience of using a lightweight formal specification method for a commercial embedded system product line", Requirements Engineering Journal 10 (2), doi:10.1007/s00766-004-0209-1
  2. Leveson, Nancy; Heimdahl, Mats Per Erik; Hildreth, Holly; Reese, Jon Damon (1994), "Requirements Specification for Process-Control Systems", IEEE Transactions on Software Engineering 20 (9), doi:10.1109/32.317428

Pour en savoir plus[modifier | modifier le code]

  • Michael Sipser: Introduction to the Theory of Computation. PWS Publishing Co., Boston 1997 (ISBN 0-534-94728-X)