Table de transition d'état

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

Dans la Théorie des automates et Logique séquentielle, une Table de transition d'état est un tableau montrant dans quel état (or states in the case of a nondeterministic finite automaton) d'une semiautomaton finis ou Automate fini se déplacer, sur la base de l'état actuel et les autres entrées. Une table d'état est essentiellement une table de vérité, dans lequel 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 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]

il est aussi appelé tableaux caractéristiques, les tables d'état à une dimension sont beaucoup plus comme 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]

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 (ligne / colonne intersections) dans la table contiennent l'état suivant si un événement se produit (et éventuellement l'action liée à cet état transition).
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]

Transitions simultanées dans plusieurs machines à états finis peut être démontré dans ce qui est effectivement un tableau à n dimensions état de transition dans lequel des paires de rangées carte (ensembles de) états actuels à des états suivants[1]. Il s'agit d'une alternative à la communication entre les différents représentant, 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: "AND/OR tables" [2] sont similaires aux tables de décision incomplets où la décision pour les règles qui sont présents implicitement l'activation de l'associé transition.

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
  Table de transition d'état
DFAexample.svg

Toutes les entrées possibles de la machine sont énumérés dans les colonnes de la table. Tous les états possibles sont énumérés dans les rangées. De la table de transition d'état ci-dessus, il est facile de voir que si la machine est en S1 (la première ligne), et l'entrée suivante est le caractère 1, la machine restera dans S1. Si un 0 caractère arrive, la machine transition vers S2 comme on peut le voir à partir de la deuxième colonne. Dans le diagramme cela est indiqué par la flèche de S1 à S2 marqué par un 0.

Pour un automate fini non déterministe (NFA), une nouvelle entrée peut causer la machine d'être dans plus d'un État, d'où son non-déterminisme. Ceci est indiqué dans un tableau de transition d'état par une paire d'accolades { } avec l'ensemble des états cibles entre eux.

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 lecture d'une entrée de 0 , que ce soit 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 NFA pour passer à un état différent lorsqu'il est administré 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 l'automate fini non déterministe décrit.

Transformations de / vers diagramme d'état[modifier | modifier le code]

Il est possible de dessiner un diagramme d'état 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 d'en tirer une flèche à l'état de destination (s). Il peut y avoir plusieurs flèches pour un caractère d'entrée si l'automate est un NFA.
  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 en acceptant l'état. 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