Les automates d'états finis

Updated 1,008 Days AgoPublic

Actions

Les automates d'états fini

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ère 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 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

Exercice

• Écrivez un algorithme qui valide la saisie d'un nombre flottant positif ou négatif. Le schémas d'un tel automate est le suivant:

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<-c
                état<-2
            FIN SI
        CAS 2:
            LIRE c

            SI c>='0' ET c<='9':
                nbr<-c
                état<-2
            SINON SI c=='.':
                nbr<-c
                état<-3
            SINON SI c=CR:
                état<-4
            FIN SI

        CAS 3:
            LIRE c

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

ECRIRE "Votre nombre est: ", nbr
FIN

• Écrivez un automate qui compte le nombre de mots d'une phrase, commençant par une majuscule et terminant par un point. La phrase ne peut contenir deux espaces consécutifs.
• Écrivez un automate qui compte le nombre de couples 'L', 'E', d'une phrase, terminée par un point.
• Écrivez un automate qui demande la saisie d'une date au format JJ/MM/ANNEE
• Écrivez un automate qui transforme une phrase en "Gaulois". Pour y parvenir, ajoutez "ix", si un mot commence par une voyelle. Si le mot commence par une consonne, déplacez celle-ci à la fin du mot et rajoutez le suffix "um". Exemple: VITRE -> ITREVUM, MARTIN -> ARTINMUN, ALBUM -> ALBUMIX)