Cet outil sert à la manipulation d’automates : déterminisation, réduction, suppression des 𝜀-transitions, calcul d’expression régulières équivalentes... Le but de cet outil est de pouvoir vérifier ses réponses, et non de les trouver. Vous pouvez vous déplacer sur l’interface, et dézoomer au besoin, si vous réalisez des automates ayant un grand nombre d’états.

L’éditeur d’automates a deux “modes” : ajout d’état ou ajout de transitions. Les deux premiers boutons du menu permettent de passer respectivement au mode “ajout d’états” et “ajout de transitions.”

En mode ajout d’état, un double-click permet d’ajouter un état. Les états sont automatiquement numérotés. Un click sur un état lui fera changer de type d’état : état normal, état initial (bordure grasse), état final (double bordure). Les états peuvent être déplacés.

En mode ajout de transitions, un click définit l’état de départ de la transition, puis un second click définit l’état d’arrivée de la transition. L’étiquette de la transition est ensuite demandée. Pour obtenir une transition qui “boucle” sur un état, il suffit de faire un double-click sur l’état concerné. Pour obtenir une 𝜀-transition, il suffit d’entrer le caractère ‘&’ comme étiquette de transition. Les transitions sont automatiquement regroupées si elles ont mêmes états de départ et d’arrivée, et les étiquettes sont affichées séparées par des virgules.

Les autres boutons permettent la manipulation d’automates. Attention : les états peuvent changer de place (et même de nom dans le cas de la déterminisation) après la manipulation.

• L’action “𝗋𝗆_𝜀” supprime les 𝜀-transitions de l’automate, en conservant le même langage.
• L’action “𝖽𝖾𝗍” déterminise l’automate. L’automate est automatiquement réduit après la déterminisation en utilisant l’algorithme de Brzozowski.
• L’action “𝖼𝗈𝗆𝗉” complète l’automate en ajoutant un état “poubelle.”

Les actions suivantes opèrent sur les langages des automates, et les expressions régulières.

• L’action “→ Reg” détermine une expression régulière ayant même langage que l’automate, par élimination d’états.
• L’action “← Reg” crée un automate à partir d’une expression régulière, par la construction de Thompson.
• L’action “∈ ℒ” teste l’appartenance d’un mot 𝑤 dans le langage de l’automate.

Des menus contextuels (ouverts avec un click droit) permettent de réaliser plus d’actions. Ces menus diffèrent en fonction de l'objet sélectionné (transition, état, ou aucun objet).

• En sélectionnant un état, on peut le supprimer, les transitions entrantes et sortantes sont également supprimées. On peut également le transformer en état final ou initial, ces actions fonctionnent en “toggle” : l’action “passer en final” transformera un état final en état normal, et de même pour l’action “passer en initial.”
• En sélectionnant une transition, on peut la supprimer, ou changer son étiquette. La supprimer ne supprimera pas les états associés.
• En ne sélectionnant aucun objet, on peut supprimer tous les états et transitions, annuler la dernière action ou la refaire.

Des raccourcis claviers permettent de réaliser certaines tâches plus facilement. Pour passer en mode “ajout d’état,” on peut appuyer sur ‘s.’ Pour passer en mode “ajout de transitions,” on peut appuyer sur ‘t.’ Pour annuler la dernière action, on peut appuyer sur ‘Ctrl+Z.’ Pour refaire la dernière action annulée, on peut appuyer sur ‘Ctrl+Shift+Z’ ou ‘Ctrl+Y.’

L’agencement des automates est réalisé automatiquement en utilisant un modèle basé sur la loi de Hooke (pour les transitions), la loi de Coulomb (pour les états) et des frottements pour la convergence des positions. L’agencement obtenu n’est pas idéal, mais il est généralement bien mieux que celui obtenu en plaçant les nœuds sur une grille ou sur un cercle.

Ce projet a été réalisé dans le cadre du soutien en informatique en prépa MPI^(⋆|𝜀) par Hugo SALOU. En cas de bug, merci de me contacter via Discord (username : hugos29).