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.

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

Tables d'état à une dimension

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

S₁ et S₂ 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

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

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. 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" 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

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

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 S₁ (la première ligne), et l'entrée suivante est 1, la machine restera dans l'état S₁. Un 0 permet à la machine d'entamer une transition vers l'état S₂ comme indiqué dans la deuxième colonne. C'est ce qui est représenté dans le diagramme par la flèche allant de S₁ à S₂ 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 S₁ qui lit une entrée de 0, sera dans deux états en même temps, les États S₂ et S₃. 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 S₃, la NFA peut se déplacer à S₁ 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

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

Excitation table

Pour en savoir plus

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