Lorsque plusieurs personnes collaborent sur un même projet, elles sont régulièrement amenées à échanger des documents, par exemple des diagrammes représentant le fonctionnement du système à développer. Il est nécessaire que tous les acteurs du projet soient d’accord sur la façon d’interpréter ces diagrammes. S’il y a des ambiguïtés ou des malentendus, le projet peut aboutir à un système qui ne fonctionnera pas de la manière attendue.

Une manière de mettre tout le monde d’accord consiste à choisir des représentations qui s’appuient sur des modèles mathématiques. Ainsi, il devient possible de vérifier rigoureusement si un circuit réalise bien le comportement spécifié. Et cette vérification peut même être automatisée.

Dans ce chapitre, nous donnons un rapide aperçu de la théorie des automates finis tels qu’ils sont utilisés dans le domaine de la conception de circuits logiques. Cet exposé est illustré par l’exemple de la commande d’un robot autonome pour lequel nous avons proposé deux graphes d’états.

Définition générale

Un automate fini est défini par un sextuplet $(S, I, Q, s_0, f_T, f_Q)$ où :

$S$ est l’ensemble des états possibles.
$I$ est l’ensemble des entrées possibles.
$Q$ est l’ensemble des sorties possibles.
$s_0$ est l’état initial ( $s_0 \in S$ ).
$f_T$ est la fonction de transition qui définit l’état suivant en fonction de l’état courant et de la valeur courante des entrées.
$f_Q$ est la fonction de sortie qui définit la valeur de sortie en fonction de l’état courant, et éventuellement de la valeur courante des entrées.

Dans un automate fini, l’ensemble $S$ contient un nombre fini d’éléments.

Progression de l’état et calcul des sorties

Le fonctionnement d’un automate fini est rythmé par l’arrivée de ses entrées. On notera $i_0, i_1,\ldots i_N$ la séquence des entrées présentées à la machine dans l’ordre chronologique.

Initialement, l’automate est dans l’état $s_0$ . Lorsque survient l’entrée $i_0$ , l’automate produit une sortie $q_0 = f_Q(s_0, i_0)$ et passe dans l’état $s_1 = f_T(s_0, i_0)$ .

Ensuite, au cours du fonctionnement de l’automate, l’arrivée d’une nouvelle entrée $i_k$ produit une sortie $q_k = f_Q(s_k, i_k)$ et une mise à jour de l’état $s_{k+1} = f_T(s_k, i_k)$ .

Par la suite, pour alléger les notations, nous noterons simplement $s$ , $i$ et $q$ l’état, l’entrée et la sortie courants (au lieu de $s_k$ , $i_k$ et $q_k$ ). L’état suivant sera noté $s^*$ (au lieu de $s_{k+1}$ ).

Signature des fonctions de transition et de sortie

La fonction de transition aura la signature suivante :

f_T : \left\{ \begin{array}{ccc} S\times I & \rightarrow & S \\ (s, i) & \mapsto & s^* \end{array} \right.

Dans un machine de Moore, les sorties ne dépendent que de l’état courant. La signature de la fonction de sortie est alors :

f_{Q,Moore} : \left\{ \begin{array}{ccc} S & \rightarrow & Q \\ s & \mapsto & q \end{array} \right.

Dans une machine de Mealy, les sorties dépendent de l’état courant et de la valeur courante des entrées. Voici la signature correspondante de la fonction de sortie :

f_{Q,Mealey} : \left\{ \begin{array}{ccc} S\times I & \rightarrow & Q \\ (s, i) & \mapsto & q \end{array} \right.

L’ensemble des états

Notre robot possède quatre états, que nous allons abréger en $S_{RM}$ (Recherche d’un Mur), $S_{SM}$ (Suivi d’un Mur), $S_{RG}$ (Rotation à Gauche) et $S_{RD}$ (Rotation à Droite). L’ensemble des états et l’état initial se définissent donc comme :

\begin{aligned} S &= \{S_{RM}, S_{SM}, S_{RG}, S_{RD}\} \\ s_0 &= S_{RM} \end{aligned}

L’ensemble d’entrées

Le robot se dirige dans le labyrinthe en se fiant aux informations fournies par ses capteurs. Lorsqu’il tourne à gauche ou à droite, il réagit également à un signal indiquant la fin d’une rotation de 90 degrés. L’ensemble des entrées possibles se définit ainsi comme l’ensemble de tous les triplets de booléens $(CA, CG, FR)$ (Capteur Avant, Capteur Gauche, Fin de Rotation) :

I = \{0,1\}^3

L’ensemble de sorties

Les actions du robot consistent à commander chaque moteur dans le sens avant ou arrière. Nous avons identifié trois actions (avancer, tourner à droite, tourner à gauche), correspondant à trois combinaisons des commandes des moteurs. Nous y ajoutons une combinaison correspondant à l’arrêt des deux moteurs (toutes les commandes à zéro). L’ensemble des sorties possibles est donc un ensemble de quadruplets de booléens $(MGA, MGR, MDA, MDR)$ (Moteur Gauche Avancer, Moteur Gauche Reculer, Moteur Droit Avancer, Moteur Droit Reculer) défini comme suit :

Q = \{(0,0,0,0), (1, 0, 1, 0), (1, 0, 0, 1), (0, 1, 1, 0)\}

La fonction de transition

La fonction de transition $f_T$ est la traduction, en termes mathématiques, des transitions du graphe d’états. Elle est de la forme :

s^* = f_T(s, CA, CG, FR)

Dans le tableau ci-dessous, chaque ligne correspond à une flèche du graphe d’états :

$s$	$CA$	$CG$	$FR$	→	$s^*$
$S_{RM}$	0	0	–	→	$S_{RM}$
$S_{RM}$	0	1	–	→	$S_{SM}$
$S_{RM}$	1	–	–	→	$S_{RD}$
$S_{SM}$	0	1	–	→	$S_{SM}$
$S_{SM}$	–	0	–	→	$S_{RG}$
$S_{SM}$	1	1	–	→	$S_{RD}$
$S_{RG}$	–	–	0	→	$S_{RG}$
$S_{RG}$	–	–	1	→	$S_{RM}$
$S_{RD}$	–	–	0	→	$S_{RD}$
$S_{RD}$	–	–	1	→	$S_{RM}$

La fonction de sortie

Dans la section précédente, nous avons proposé deux graphes d’états. Le premier décrivait une machine de Moore, où les sorties ne dépendent que de l’état courant. La fonction de sortie correspondante est de la forme :

(MGA, MGR, MDA, MDR) = f_{Q,Moore}(s)

Les valeurs des sorties associées à chacun des états sont détaillées dans ce tableau :

$s$	→	$MGA$	$MGR$	$MDA$	$MDR$
$S_{RM}$	→	1	0	1	0
$S_{SM}$	→	1	0	1	0
$S_{RG}$	→	0	1	1	0
$S_{RD}$	→	1	0	0	1

Le second graphe d’états décrivait une machine de Mealy, où les sorties dépendent de l’état courant et des entrées. La fonction de sortie correspondante est de la forme :

(MGA, MGR, MDA, MDR) = f_{Q,Mealy}(s, CA, CG, FR)

Les valeurs des sorties associées à chacun des états sont détaillées dans ce tableau :

$s$	$CA$	$CG$	$FR$	→	$MGA$	$MGR$	$MDA$	$MDR$
$S_{RM}$	0	–	–	→	1	0	1	0
$S_{RM}$	1	–	–	→	0	0	0	0
$S_{SM}$	0	1	–	→	1	0	1	0
$S_{SM}$	1	–	–	→	0	0	0	0
$S_{SM}$	–	0	–	→	0	0	0	0
$S_{RG}$	–	–	0	→	0	1	1	0
$S_{RG}$	–	–	1	→	0	0	0	0
$S_{RD}$	–	–	0	→	1	0	0	1
$S_{RD}$	–	–	1	→	0	0	0	0

Résumé

Un automate fini est défini mathématiquement par un ensemble d’états, un ensemble d’entrées, un ensemble de sorties, un état initial, une fonction de transition et une fonction de sortie.

La fonction de transition détermine l’état suivant en fonction de l’état courant et de la valeur des entrées.

Pour une machine de Moore, la fonction de sortie détermine la valeur des sorties en fonction de l’état courant. Pour une machine de Mealy, la fonction de sortie détermine la valeur des sorties en fonction de l’état courant et de la valeur des entrées.

Définition mathématique des automates finis