Le logiciel automate

de l'Université Pierre Mendès-France, Grenoble

UFR Informatique et Mathématiques en Sciences Sociales

http://brassens.upmf-grenoble.fr/IMSS/logiciels/

Guide pour l'utilisation

Jean-François Perrot

1. I. Fonctionnement de base
   1. Le carré central
   2. Le rectangle Expression régulière
   3. Le rectangle Automate non déterministe
   4. Les deux rectangles Automate déterministe et Automate déterministe minimal
   5. Les quatre flèches
   6. Exemple 1 
   7. Exemple 2
      
      
2. II. Raffinements
   1. Le menu Options de la fenêtre principale.
      1. Compilation 
      2. Déterminisation
      3. Minimisation
      4. DéCompilation
   2. Le menu placement de la fenêtre d'édition des automates
   3. Un exemple substantiel

I. Fonctionnement de base

1. Le carré central

   commande l'ouverture d'une fenêtre d'aide.
   Cette aide contient des rappels de théorie plutôt qu'un mode d'emploi,
   à l'exception de la sous-rubrique édition de la rubrique Automates à états finis (sic)
   
   
   
   
   qui explique parfaitement comment utiliser l'éditeur graphique pour automates finis (voir plus loin).
   
   Attention ! Le sommaire ne dévoile pas toutes le richesses de ce module ! Ne manquez pas de consulter aussi l'index !
   
   
   
   
   
   

2. Le rectangle Expression régulière

   est l'un des deux points d'entrée du système (ses états initiaux si on le voit comme un automate fini).
   Il commande l'ouverture d'une fenêtre spécialisée, avec deux zones éditables :
   
   
   
   
   
   • Notons que le champ Vocabulaire sera rempli automatiquement à partir de la donnée de l' Expression.
     
     
   • L'icône de sauvegarde commande l'envoi de l'expression (en tant que chaîne de caractères) dans un fichier en Rich Text Format ".rtf".
     
     
   • Ce fichier peut être travaillé (ou produit) avec un éditeur de textes quelconque (p.ex. WordPad),
     et ensuite relu grâce à l'icône de lecture.
     
     

3. Le rectangle Automate non déterministe

   est l'autre point d'entrée du système.
   Il commande l'ouverture d'une fenêtre d'édition d'automates,
   soit en mode graphique, soit sous forme textuelle (table de transitions).
   
   
   
   
   
   Sur l'emploi de l'éditeur graphique, voir l'aide comme indiqué ci-dessus (à lire plusieurs fois !).
   
   L'icône de sauvegarde envoie le contenu dans un fichier au format spécial ".aut",
   qui peut ensuite être relu via l'icône de lecture.
   
   En cliquant sur Placement, on provoque un réarrangement du graphe de l'automate, par exemple :
   
   
   
   
   En cliquant sur INV on fait apparaître l'automate (non-déterministe) inverse :
   
   
   
   
   On note que l'option C++ est désactivée : voir plus loin.
   
   
   

4. Les deux rectangles Automate déterministe et Automate déterministe minimal

   sont initialement inertes, alors que les deux précédents sont actifs, ouvrant au besoin des fenêtres vides.
   Répétons-le, Expression régulière et Automate non déterministe sont les deux seuls point d'entrée du système.
   
   Lorsqu'ils contiennent effectivement des automates (suite à un calcul, voir ci-dessous), les deux autres rectangles commandent l'ouverture de fenêtres d'édition pour ces automates, du même modèle que dans le cas non-déterministe.
   Dans ces fenêtres, l'utilisateur peut déplacer à sa guise les sommets et les arcs ... mais toute tentative de modification autre que le placement provoquera un retour au non-déterminisme !
   En somme, les automates transformés ne peuvent pas être modifiés - ni a fortiori lus dans un fichier : la commande de lecture est sans effet dans ces fenêtres.
   
   Dans le cas déterministe minimal, l'option C++ est activée, elle commande la traduction de l'automate en C++,
   avec deux choix de style possibles : avec ou sans GOTO.
   
   
   
   
   
   
   
   
   

5. Les quatre flèches

   symbolisent chacune une transformation, clairement définie par les noms de ses rectangles source et but (génération d'un automate non-déterministe à partir d'une expression régulière, déterminisation d'un automate non-déterministe, réduction d'un automate déterministe, et production d'une expression régulière à partir d'un automate minimal). 
   
   
   • En cliquant sur la flèche on commande l'exécution de la transformation correspondante appliquée à l'objet contenu dans le rectangle-source et le "remplissage" du rectangle-but avec la donnée transformée.
     
     
   • Si le rectangle-source contient effectivement une donnée, la flèche qui était blanche passe au rouge pour indiquer que l'opération a eu lieu. Sinon, elle reste blanche.
     
     
   • Si le rectangle-but contient un automate, son affichage n'est pas automatique, il faut cliquer sur le rectangle pour  provoquer cet affichage (ce qui permettra, au besoin, de sauvegarder l'automate). L'expression régulière, en revanche, est immédiatement affichée.
     
   
   

6. Exemple 1 :

   en partant de l'expression xy*xx*y comme ci-dessus, on obtient successivement :
   
   
   
   
   (noter l'abondance des ε-transitions)
   
   
   
   et enfin
   
   
   
   voir ci-dessus pour la traduction en C++.
   
   

7. Exemple 2

   en partant de l'automate construit avec l'éditeur graphique
   
   
   
   
   renversé (pour changer un peu)
   
   
   
   
   
   on obtient successivement :
   
   
   
   
   
   
   On observe que l'automate déterministe était déjà réduit...
   
   Et enfin l'expression rationnelle :
   
   

II. Raffinements

1. Le menu Options de la fenêtre principale.

   
   
   
   
   Pour interpréter ses quatre rubriques, rappelons que Compilation désigne la construction de l'automate (a priori non-déterministe) à partir de l'expression. Les quatre rubriques du menu gouvernent donc les quatre opérations associées aux quatre flèches de la fenêtre.
   
   

   1. Compilation 

      Cette option règle deux questions à la fois :
      
      • le choix de la grammaire précisément retenue pour écrire les expressions (voir l'aide pour plus de détails)
      • le choix de l'algorithme de construction.
        
      Elle permet en outre de demander la visualisation immédiate de l'automate obtenu, avec une trace du calcul.
      
      
      
      
      
      
      

   2. Déterminisation

      Cette option permet de suivre le déroulement du calcul, pas à pas.
      
      
      
      
      Suite de l'exemple précédent
      
      
      
      
      

   3. Minimisation

      Cette option permet de choisir son algorithme parmi 3 candidats, et aussi de le regarder fonctionner.
      
      
      
      
      Suite de l'exemple précédent
      
      
      
      
      

   4. DéCompilation

      Calcul de l'expression (dans notre exemple : xy*xx*y) à partir de l'automate minimal.
      Ici aussi, l'option offre un choix entre 3 procédés, et la possibilité de suivre le calcul pas à pas.
      
      
      
      
      
      
      
      
      
      

2. Le menu placement de la fenêtre d'édition des automates

   Il est sans doute prévu d'offrir un choix de plusieurs procédés pour disposer élégamment le graphe d'états dans la fenêtre, mais pour l'instant un seul est implémenté.
   
   
   
   
   
   Toutefois, en cliquant sur ce choix unique on peut encore choisir entre deux manières de réaliser les forces en question :
   
   
   
   
   
   Ce réglage par défaut conduit au placement illustré plus haut.
   En choisissant la technique avec ressorts seuls :
   
   
   
   
   
   on obtient effectivement une disposition différente !
   
   
   
   
   
   

3. Un exemple substantiel (merci à Claude Del Vigna)

   Cooccurrence de "bonjour" et de "bonbon" : en utilisant la syntaxe étendue (choix extensions dans l'option Compilation) l'expression s'écrit :
   
   (b|o|n|j|u|r|Z)*bonjour(b|o|n|j|u|r|Z)* & (b|o|n|j|u|r|Z)*bonbon(b|o|n|j|u|r|Z)*
   
   où le méta-caractère Z désigne tous les caractères de l'alphabet qui ne sont ni dans bonbon, ni dans bonjour.
   
   
   1. On constate d'abord que le choix de la syntaxe étendue entraîne par défaut un autre choix pour l'algorithme de construction :
      
      
      
      
      
      et que ce choix conduit à passer directement à un automate déterministe :
      
      
      
      
      
      
   2. On lance le calcul de l'automate à partir de l'expression :
      
      
      
      
      
      Pour pour afficher l'automate comme suit, on a choisi le placement par ressorts seuls, de taille 90 :
      
      
      
      
      
      
   3. L'automate minimal étant moins compliqué, on obtient un affichage convenable avec des ressorts de taille 115 :
      
      
      
      
      
   4. Pour calculer l'expression rationnelle correspondante (en syntaxe standard !), l'algorithme de "décompilation" de McNaughton & Yamada utilisé précédemment prend un temps de calcul prohibitif. Mais en choisissant le procédé par réduction d'états, on obtient la solution en une fraction de seconde :