Les automates d’états finis

Les automates sont une façon de concevoir les programmes informatiques. Il s’agit de prévoir une séquence où chaque état impose un traitement spécifique. Le programme ne peut être que dans un seul état à la fois, et donc n’effectuer qu’un seul traitement. Il peut ensuite passer d’un état à un autre en passant par une condition. Ce passage d’un état à un autre est appelé une transition.

On rencontre couramment des automates finis dans de nombreux appareils qui réalisent des actions déterminées en fonction des événements qui se présentent. Un exemple est un distributeur automatique de boissons qui délivre l’article souhaité quand le montant introduit est approprié. D’autres exemples sont les ascenseurs qui savent combiner les appels successifs pour s’arrêter aux étages intermédiaires, les feux de circulation qui savent s’adapter aux voitures en attente, les digicodes qui analysent la bonne suite de chiffres.

Les automates sont très souvent modélisés à l’aide d’un schéma. Celui-ci est composé de cercle, les états, et de flèche, les transitions. Les conditions des transitions sont entre crochets. Dans les exemples ci-dessous, nous utiliserons la notation [0-9] pour signaler les caractères de 0 à 9. Le diagramme ci-dessous représente l’automate validant l’entrée par l’utilisateur d’un entier positif ou négatif. Au départ de l’automate, l’utilisateur doit entrer un caractère. S’il entre un symbole + ou -, il transite dans l’état 1. Par la suite, l’utilisateur n’a plus que la possibilité d’entrer que des chiffres. Une fois fait, l’automate transite dans l’état numéro 2. Là, l’utilisateur peut valider sa saisie à l’aide de la touche ENTER, ou entrer un autre nombre.

Les automates sont généralement programmés à l’aide d’une boucle RÉPÉTER... TANT QUE, et contiennent une condition pour chacun des états. Étant donné que le nombre de conditions explose très rapidement, il existe l’instruction SELON... CAS ...: qui permettent de simplifier l’écriture. Il faut savoir également que cette instruction est tout spécifiquement optimisée pour tester une seule variable sur un ensemble de valeur. L’ordinateur sautera directement sur le bon cas, sans devoir évaluer un ensemble de condition. Il est évidemment possible d’utiliser cette structure pour d’autres algorithmes que les automates. Le diagramme ci-dessus peut être implémenter de la manière suivante:

DÉBUT
VARIABLE état: ENTIER
VARIABLE c: CARACTÈRE
VARIABLE nombre: CHÂINE

nbr<-""
état<-0
RÉPETER
    SELON état:
        CAS 0:
            LIRE c

            SI c=='+' OU c=='-':
                nbr<-c
                état<-1
            SINON SI c>='0' ET c<='9':
                nbr<-c
                état<-2
            FIN SI
        CAS 1:
            LIRE c

            SI c>='0' ET c<='9':
                nbr<-nbr+c
                état<-2
            FIN SI
        CAS 2:
            LIRE c

            SI c>='0' ET c<='9':
                nbr<-nbr+c
                état<-2
            SINON SI c=CR:
                état<-3
            FIN SI
    FIN SELON
TANT QUE état != 3

ECRIRE "Votre nombre est: ", nbr
FIN