deutsch     english    français     Imprimer

 

10.6 AUTOMATES FINIS

 

 

INTRODUCTION

 

Il est nécessaire de définir exactement ce qu’est un ordinateur avant de pouvoir déterminer dans quelle mesure il est capable de résoudre tel ou tel problème. Le célèbre mathématicien et informaticien Alan Turing publia une étude à ce sujet en 1936, bien avant que le premier ordinateur digital programmable n’existe. La machine de Turing, baptisée ainsi en l’honneur de Turing, passe successivement par différents états de manière programmée sur la base de données lues sur une bande et écrites sur cette même bande. Cette notion fondamentale qui touche au fonctionnement de l’ordinateur est encore valable actuellement puisque tous les processeurs présents dans nos ordinateurs sont en fait des machines de Turing qui passent d’un état à l’autre à la cadence de l’horloge. Cependant, les machines à états qui peuvent être modélisées par un graphe de transition se prêtent mieux aux application pratiques. Du fait qu’elles ne disposent que d’un nombre fini d’états, on les appelle des automates finis (finite-state machines en anglais).

PROGRAMMING CONCEPTS:
Machine de Turing, machines (automates) finis, machine de Mealy, graphe de transition, théorie des langages formels

 

 

LA MACHINE ESPRESSO COMME MACHINE DE MEALY

 

Chaque jour, nous sommes tous confrontés à des appareils et machines qui peuvent être considérés comme des automates parmi lesquels on trouve les distributeurs automatiques de boissons ou de billets de banque, les machines à laver et tant d’autres. Un ingénieur ou un informaticien développant de telles machines se doit de comprendre clairement qu’elles effectuent leur tâche en passant de l’état courant à un état successeur. Ces transitions d’état sont déterminées par les entrées de l’automate, à savoir les données en provenance des capteurs ou des interrupteurs formant l’interface de commande. En fonction des données en entrée, l’opérateur actionne certains actuateurs lors de chaque transition d’états tels que des moteurs, des pompes, des témoins lumineux qui constituent les sorties de l’automate.

Dans le cas présent, nous allons développer une machine à café espresso pouvant se trouver dans trois états différents : elle peut être éteinte (OFF), allumée et en attente (STANDBY) ou en train de pomper et chauffer de l’eau pour préparer un espresso (WORKING). L’interface de contrôle de la machine comporte quatre boutons-poussoirs : turnOn, turnOff, work, et stop.

Bien qu’il soit possible de décrire le fonctionnement d’une machine à café espresso en prose, un graphe de transition est bien plus clair et explicite. Un tel graphe est formé de cercles représentant les différents états (nœuds du graphe) et de flèches (arête orientée) passant d’un état à l’autre et formalisant les transitions d’états. Les flèches sont étiquetées par les entrées / sorties qui causent la transition en question. Il est également important de définir l’état initial de la machine lorsqu’elle est mise en fonction. Du fait que n’importe quelle touche peut être actionnée dans n’importe lequel des états, toutes les entrées doivent être envisagées à chaque état. Si aucune action n’est effectuée, la sortie est omise.

Graphe de transition :

On résume souvent le comportement de la machine dans un tableau qui spécifie pour chaque état s et chaque entrée t (ici les boutons actionnés) l’état successeur s'. L’état initial est dénoté par une étoile.

Table de transition:

 t =        s =  OFF(*)  STANDBY  WORKING
 turnOff  OFF  OFF  OFF
 turnOn  STANDBY  STANDBY  WORKING
 stop  OFF  STANDBY  STANDBY
 work  OFF  STANDBY  WORKING

En termes mathématiques, on peut dire que l’état successeur s' est une fonction de l’état courant et de l’entrée : s' = F(s, t). La fonction F est appelée fonction de transition.

On peut également spécifier dans un tel tableau les sorties correspondant à chaque état et chaque donnée en entrée :

Table de sortie:

 t =        s =  OFF(*)  STANDBY  WORKING
 turnOff  -  LED éteinte  LED éteinte, Pompe allumé
 turnOn  LED allumée  -  -
 stop  -  -  Pump éteinte
 work  -  Pump allumée  -

À nouveau, on peut dire que, mathématiquement, la sortie g est une fonction de l’état courant et des entrées : g = G(s, t). G est appelée fonction de sortie.

 

 

MEMENTO

 

Tout ceci, à savoir les différents états, les valeurs en entrée, les valeurs en sortie ainsi que les fonctions de transition et de sortie forment une machine de Mealy.

 

 

IMPLÉMENTATION DE LA MACHINE ESPRESSO AVEC DES CHAÎNES DE CARACTÈRES

 

La pression d’un bouton devrait engendrer une transition d’un état à l’état suivant. Les 4 touches directionnelles du clavier serviront à simuler les boutons de la machine et spécifient les valeurs en entrée. L’implémentation est relativement triviale : le programme attend qu’une touche soit enfoncée au sein d’une boucle d’événements (event loop) infinie avec getKeyEvent(). Selon la valeur de retour de getKeyEvent(), l’état courant est modifié d’après la table de transition et les sorties sont calculées en fonction de la table de sortie.

from gconsole import *

def getEntry():
    keyCode = getKeyCodeWait()
    if keyCode == 38: # up  
        return "stop"
    if keyCode == 40: # down
        return "work"
    if keyCode == 37: # left
        return "turnOff"
    if keyCode == 39: # right
        return "turnOn"
    return ""
    
state = "OFF"  # Start state
makeConsole()
while True:
    gprintln("State: " + state)
    entry = getEntry()
    if entry == "turnOff":
       if state == "STANDBY":
            state = "OFF"
            gprintln("LED off")
       if state == "WORKING":
            state = "OFF"
            gprintln("LED and pump off")
    elif entry == "turnOn":
        if state == "OFF":
            state = "STANDBY"
            gprintln("LED enabled")
    elif entry == "stop":
        if state == "WORKING":
            state = "STANDBY"
            gprintln("Pumpe off")
    elif entry == "work":
        if state == "STANDBY":
            state = "WORKING"
            gprintln("Pumpe enabled")
Sélectionner le code (Ctrl+C pour copier, Ctrl+V pour coller)

 

 

MEMENTO

 

Seuls les événements qui mènent à un changement d’état ou qui génèrent une sortie sont traités au sein de la boucle d’événements.

La fonction makeConsole() permet de créer une fenêtre d’entrée / sortie très simple qui accepte des saisies de caractères individuels au clavier sans la nécessité de devoir appuyer sur <return> pour être validés. La fonction getKeyCodeWait() met le programme en attente de la pression d’une touche du clavier et retourne le code de la touche pressée. La documentation du module gconsole se trouve dans l’aide de TigerJython sous Aide / APLU documentation.

 

 

TYPES ÉNUMÉRÉS COMME ÉTATS ET IDENTIFIANTS D’ÉVÉNEMENTS

 

Puisque les automates fonctionnent sur la base d’états, de valeurs en entrée et de valeurs en sortie, il serait avantageux d’introduire une structure de données particulière spécialement adaptée. De nombreux langages de programmation mettent à disposition un type de données particulier pour les énumérations. Malheureusement, ce type de données n’est pas présent dans la syntaxe du langage Python standard. Heureusement, il a été ajouté à TigerJython grâce au mot-clé additionnel enum() qui permet de définir des valeurs énumérées à partir de chaines de caractères respectant les contraintes et conventions de nommage en vigueur pour les noms de variables.

from gconsole import *

def getEvent():
    keyCode = getKeyCodeWait()
    if keyCode == 38: # up  
        return Events.stop
    if keyCode == 40: # down
        return Events.work
    if keyCode == 37: # left
        return Events.turnOff
    if keyCode == 39: # right
        return Events.turnOn
    return None
    
State = enum("OFF", "STANDBY", "WORKING")
state = State.OFF
Events = enum("turnOn", "turnOff", "stop", "work")
makeConsole()
while True:
    gprintln("State: " + str(state))
    event = getEvent()
    if event == Events.turnOn:
        if state == State.OFF:
            state = State.STANDBY
    elif event == Events.turnOff:
            state = State.OFF
    elif event == Events.work:
        if state == State.STANDBY:
            state = State.WORKING
    elif event == Events.stop:
        if state == State.WORKING:
            state = State.STANDBY
Sélectionner le code (Ctrl+C pour copier, Ctrl+V pour coller)

 

 

MEMENTO

 

Il est de votre ressort de décider si vous voulez ou non utiliser le type de données additionnel enum. Son usage ne rend pas les programmes plus courts mais plus lisibles et sécurisés du fait que seules les valeurs explicitement spécifiées dans le type énuméré seront reconnues et autorisées.

 

 

IMPLÉMENTATION DE LA MACHINE ESPRESSO AVEC CONTRÔLE DE LA SOURIS

 

Il suffit d’un petit effort supplémentaire pour mettre sur pied une simulation graphique de la machine Espresso en utilisant la bibliothèque JGameGrid, ce qui ne manquera pas de rendre la simulation encore plus claire et amusante. En lieu et place des quatre touches directionnelles du clavier, les quatre entrées sont actionnées par des clics de souris sur des boutons simulés et la sortie de la LED et du pompage sont immédiatement rendus visibles par des images de sprite. Au lieu d’utiliser une boucle d’événements, il est fait usage de la fonction de rappel pressEvent() qui sera toujours invoquée lors d’un clic de souris sur l’image de la machine avec la souris. Puisque l’on utilise une grille comportant 7 x 11 cellules en tant que GameGrid, il est possible de capturer les clics effectués sur les boutons virtuels à l’aide des coordonnées grille.

 

from gamegrid import *

def pressEvent(e):
    global state
    loc = toLocationInGrid(e.getX(), e.getY())
    if loc == Location(1, 2): # off
        state = State.OFF
        led.show(0)
        coffee.hide()
    elif loc == Location(2, 2): # on
        if state == State.OFF:
            state = State.STANDBY
            led.show(1)
    elif loc == Location(4, 2): # stop
        if state == State.WORKING:
            state = State.STANDBY
            coffee.hide()
    elif loc == Location(5, 2): # work
        if state == State.STANDBY:
            state = State.WORKING
            coffee.show()
    setTitle("State: " + str(state))
    refresh()
        
State = enum("OFF", "STANDBY", "WORKING")
state = State.OFF
makeGameGrid(7, 11, 50, None, "sprites/espresso.png", False, 
             mousePressed = pressEvent)
show()
setTitle("State: " + str(state))
led = Actor("sprites/lightout.gif", 2)
addActor(led, Location(3, 3))
coffee = Actor("sprites/coffee.png")
addActor(coffee, Location(3, 6))
coffee.hide()
refresh()
Sélectionner le code (Ctrl+C pour copier, Ctrl+V pour coller)

 

 

MEMENTO

 

Une interface utilisateur graphique permet de rendre une simulation beaucoup plus claire et attractive.

 

 

PENSER LES INTERFACES GRAPHIQUES EN TERMES D’ÉTATS

 

À première vue, les machines de Mealy semblent être confinées au monde des théories fumeuses. Mais il faut, bien au contraire, toujours penser en termes d’états lors du développement de programmes événementiels comportant une interface utilisateur graphique. En guise d’exemple, écrivons un petit programme tortue contrôlé par 3 boutons. Le bouton start_button démarre le mouvement de la tortue, le bouton stop_button l’interrompt et le bouton quit_button termine le programme. Afin d’implémenter ce programme correctement, il est nécessaire de garder en tête le graphe de transition:

 

Comme nous l’avons déjà vu à maintes reprises, il ne faut jamais effectuer le rendu d’une animation au sein des gestionnaires d’événements de l’interface graphique car ces derniers ne supportent que l’exécution d’un code très rapide. Cela vient du fait que le rendu à l’écran n’est effectué qu’à la fin de la fonction de rappel. C’est la raison pour laquelle on se contente, au sein du gestionnaire de clic sur les boutons, de modifier l’état de sorte que le mouvement de la tortue est effectué dans la partie principale du programme.

(Vous pouvez en apprendre davantage au sujet de ce problème dans l’annexe 4 Traitement parallèleg)

from javax.swing import JButton
from gturtle import *

def buttonCallback(evt):
    global state
    source = evt.getSource()
    if source == runBtn:
        state = State.RUNNING
        setTitle("State: RUNNING")
    if source == stopBtn:
        state = State.STOPPED
        setTitle("State: STOPPED")
    if source == quitBtn:
        state = State.QUITTING
        setTitle("State: QUITTING")

State = enum("STOPPED", "RUNNING", "QUITTING")
state = State.STOPPED

runBtn = JButton("Run", actionPerformed = buttonCallback)
stopBtn = JButton("Stop", actionPerformed = buttonCallback)
quitBtn = JButton("Quit", actionPerformed = buttonCallback)
makeTurtle()
setTitle("State: STOPPED")
back(100)

pg = getPlayground()
pg.add(runBtn)
pg.add(stopBtn)
pg.add(quitBtn)
pg.validate()

while state != State.QUITTING and not isDisposed():
    if state == State.RUNNING:
          forward(200).left(127)
dispose()         
Sélectionner le code (Ctrl+C pour copier, Ctrl+V pour coller)

 

 

MEMENTO

 

La structure de ce code est typique de la programmation événementielle. Vous devriez donc faire votre maximum pour la mémoriser tant elle est fréquente.

Il est nécessaire d’importer le module JButton pour utiliser les boutons qu’il faut ajouter à la fenêtre de tortue (objet Playground) à l’aide de sa méthode add(). Il faut ensuite rafraîchir la fenêtre tortue avec la méthode validate() pour que ces boutons soient visibles.

 

 

EXERCICES

 

1.


Un parcomètre n’accepte que des pièces de 1 € et 2 € qui sont à insérer l’une après l’autre. Dès que la machine a reçu suffisamment d’argent pour payer le parking, elle émet le billet et retourne la monnaie au cas où le montant inséré s’avère trop important. La taxe de parking se monte à 3 €.

En partant de l’état initial S0, la machine passe aux état S1 ou S2, selon qu’une pièce de 1 € ou de 2 €a été insérée. Elle imprime sur la sortie les valeurs « - » (rien), « K » (ticket) ou « K,R » (ticket et monnaie de retour).

a. Déterminer les tables d’entrées et de sorties de cet automate
b. Dessiner le graphe de transition du parcomètre
c. Développer, à l’aide de GConsole (voir premier exemple ci-dessus), un programme qui interprète la pression de la touche 1 du clavier comme l’insertion d’une pièce de 1 € et de la touche 2 comme l’insertion d’une pièce de 2 €.  Le programme écrira l’état subséquent ainsi que les valeurs de sortie dans la console.

 

   

MATÉRIEL SUPPLÉMENTAIRE


 

ACCEPTEURS POUR LANGAGES RATIONNELS (RÉGULIERS)

 

Un langage formel est constitué d’un alphabet de symboles et d’un jeu de règles permettant de déterminer de manière univoque si une séquence de symboles particulière appartient ou non au langage en question. S’il est possible d’implémenter les règles en utilisant un automate, on parle de langage régulier ou langage rationnel.

Comme exemple, considérons un langage très simple dont l’alphabet est constitué uniquement des lettres A et B. On peut considérer le jeu de règles comme une machine de Mealy spéciale qui n’engendre aucune valeur de sortie. En l’occurrence, la machine lit l’expression caractère après caractère en partant d’un état initial et effectue une transition vers l’état successeur sur la base du caractère lu. Si l’automate se trouve dans l’un des états finaux prédéterminés après la lecture de la séquence de caractères, l’expression en question appartient au langage. Considérons le graphe de transition suivant (S: état initial, A: état final):

Dans l’implémentation ci-dessous, le changement d’état est déclenché par la pression de la touche A ou B du clavier. Le programme imprime ensuite l’état courant et le mot saisi dans la console.

from gconsole import *

def getKeyEvent():
    global word
    keyCode = getKeyCodeWait(True)
    if keyCode == KeyEvent.VK_A:
        return Events.a
    if keyCode == KeyEvent.VK_B:
        return Events.b
    return None

State = enum("S", "A", "B")
state = State.S
Events = enum("a", "b")
makeConsole()
word = ""
gprintln("State: " + str(state))
while True:
    entry = getKeyEvent()
    if entry == Events.a:
        if state == State.A:
            state = State.S
        elif state == State.B:
            state = State.S
        word += "a"
        gprint("Word: " + word + " -> ")
        gprintln("State: " + str(state))
    elif entry == Events.b:
        if state == State.S:
            state = State.B
        elif state == State.B:
            state = State.A
        word += "b"
        gprint("Word: " + word + " -> ")
        gprintln("State: " + str(state))
Sélectionner le code (Ctrl+C pour copier, Ctrl+V pour coller)

 

 

MEMENTO

 

Un accepteur permet de déterminer si un mot donné appartient ou non au langage. Il s’agit d’un cas particulier de machine de Mealy dépourvue de valeur de sortie. Le mot appartient au langage si la lecture de ses caractères individuels permet de passer de l’état initial à un des états finaux acceptables. Le mot abbabb appartient par exemple au langage alors que ce n’est pas le cas de baabaa.

 

 

EXERCICES

 

1.


Une machine à rire ne doit accepter que les mots ha. ou haha. ou encore hahaha. etc. Le dernier caractère de la séquence est un point (.). Dessiner le graphe de transition de cette machine. Implémenter la machine correspondante en Python.

Instructions supplémentaires : introduire un état d’erreur E qu’il n’est plus possible de quitter quelle que soit l’entrée.