Les automates – Opérations et notions élémentaires

Bonjour à tous et bienvenue dans ce troisième article de la série des automates finis. Dans l’article précédent, nous avions mis en place une implémentation en Python nous permettant de manipuler des automates finis déterministes et nous allons aujourd’hui nous intéresser aux opérations et notions élémentaires des AFDs.

Prédécesseurs et successeurs

Dans un premier temps, nous allons introduire les notions de successeur et de prédécesseur d’un état. Reprenons l’automate *aaba* que nous avions créé dans le chapitre précédent :

Les successeurs d’un état q sont l’ensemble des états de destination des transitions partant de q. En d’autres termes, pour un automate A= (Q, q₀, Σ, δ, F), successors(q) = {q’ ∈ Q | ∃ s ∈ Σ : δ(q, s) = q’}.

Dans l’automate précédent, on a :  successors(0) = [0, 1], successors(1) = [0, 2], successors(2) = [2, 3], successors(3) = [0, 4], successors(4) = [4].

L’ensemble des prédécesseurs d’un état q correspond aux états qui ont (au moins) une transition allant vers q, soit : predecessors(q) = {q’ ∈ Q | ∃ s ∈ Σ : δ(q, s) = q’}. On peut également dire que les prédécesseurs de q sont les états qui ont q comme successeurs.

De la même façon, on a : predecessors(0) = [0, 1, 3], predecessors(1) = [0], predecessors(2) = [1, 2], predecessors(3) = [2], predecessors(4) = [3, 4].

Je vous propose d’implémenter les fonctions successors et predecessors pour notre API Python, que nous mettrons dans le fichier algorithms.py. Ces fonctions prennent en entrée un AFD et un état et retournent la liste des successeurs (resp. prédécesseurs) de cet état.

La fonction successors est la plus simple à créer puisqu’il nous suffit de parcourir toutes les transitions de l’état en question et de retourner la liste des états cibles. Il faut juste faire attention à ne pas compter les états deux fois :

Plutôt simple non ? Pour la fonction predecessors c’est un poil plus difficile, puisqu’il faut parcourir toutes les transitions de tous les états pour savoir si l’état cible est celui qui nous intéresse. Notez qu’une autre solution serait de simplement calculer les successeurs de tous les états et d’ajouter un état si notre état étudié est un de ses successeurs. Voici le code :

Nous pouvons maintenant tester nos deux fonctions et constater que tout fonctionne bien comme prévu :

Automate complet

Dans cette deuxième partie de l’article, nous allons nous intéresser à la notion d’automate complet.

Un AFD est dit complet, s’il chaque état possède une transition pour chaque symbole de l’alphabet. En d’autres termes, un AFD est complet si sa fonction de transition δ est totale, et incomplet si δ est partielle. Par exemple, l’automate *aaba* est complet, tandis que l’automate suivant ne l’est pas :

Cet automate, que nous appellerons abc*, reconnait les mots sur l’alphabet Σ =  {a, b, c} qui commencent par la séquence “abc”.

Note : j’ai utilisé AUDE pour dessiner cet automate, plutôt que notre fonctionnalité d’exportation d’automate en PNG. La raison est que notre implémentation actuelle n’est pas capable de regrouper les transitions de l’état 3 en une seule flèche, ce qui réduit la lisibilité. Nous ajouterons cette fonctionnalité par la suite.

Ajoutons donc la fonction is_complete qui permettra de tester si un automate est complet ou non. L’algorithme est également très simple puisqu’il va simplement falloir itérer sur chaque état et chaque symbole pour s’assurer qu’il existe une transition :

C’est très bien tout ça, mais vous vous demandez peut-être à quoi ça peut bien servir de savoir si un automate est complet ou non ?

Pour commencer, plusieurs définitions existent pour les AFDs, et certaines définissent un AFD comme un automate complet. Avec notre définition, puisque nous n’imposons pas que l’automate soit complet pour être valide, l’exécution d’un mot s’arrête s’il n’existe pas de transition pour le symbole en cours.

Certains algorithmes, notamment la négation d’un automate que nous verrons dans le prochain article, imposent que l’automate soit complet pour fonctionner. De la même manière, la minimisation qui sera l’objet de l’article encore après, est plus simple à appréhender lorsqu’on manipule un automate complet.

En pratique, il est toujours possible de transformer un automate en un automate complet équivalent (qui reconnait le même langage). Nous allons d’ailleurs implémenter cette opération de complétion d’automate avec la fonction complete.

L’algorithme de complétion d’un automate consiste à utiliser un état “puits”, non-accepteur, vers lequel on enverra toutes les transitions manquantes. Pour l’automate abc*, voilà ce que ça donne :

Cette opération donne un automate équivalent puisque Qp n’est pas accepteur. Cela dit, l’automate n’est toujours pas complet puisque Qp a été ajouté et n’a aucune transition. Par conséquent, il nous faut également faire boucler Qp sur lui même pour chaque symbole :

Et voilà, l’automate est maintenant complet. Nous pouvons maintenant passer à l’implémentation de la fonction complete. Pour ce faire, nous allons reprendre exactement le même principe : ajout de l’état puits et ajout des transitions manquantes vers l’état puits.

Nous allons tout de même faire face à une petite difficulté supplémentaire liée à notre choix d’identifier les états par leur nom : comment faire si l’état Qp existe déjà ? Nous pourrions décider de rendre ce nom d’état réservé, mais je suggère de simplement ajouter une boucle qui nous permettra de trouver un nom d’état libre :

Notre implémentation a tout de même un petit défaut : un nouvel état puits est ajouté à chaque complétion d’un automate. En effet, l’état puits est simplement un état à partir duquel n’importe quel mot est rejeté, on pourrait tout à fait imaginer réutiliser un état existant ayant cette propriété. Cependant, nous allons simplement ajouter if is_complete(dfa): return au début de notre algorithme.

Notez également que je retourne l’automate passé en paramètre. C’est une technique fréquente qui va nous permettre d’écrire du code tel que a2 = complete(a.clone()) plutôt que de devoir ajouter une ligne pour cloner un automate lorsque c’est nécessaire.

Je vous propose donc d’essayer nos nouvelles fonctions avec l’automate abc*, dont je vous donne ci-dessous le fichier .dfa correspondant :

Essayons donc de tester nos algorithmes :

La complétion de l’automate abc* a bien fonctionné, et comme attendu, *aaba* est reconnu comme complet. Par contre, il faut admettre que notre incapacité à regrouper les transitions lors de l’exportation en PNG rend le résultat difficile à lire :

Avant de clore cette partie sur la complétion d’automates, je vous propose de modifier notre implémentation de to_dot de manière à proposer cette option de regroupement des transitions.

Je ne vais pas vous détailler les modifications du code, j’ai simplement transformé les arguments optionnels en utilisant les keyword arguments de manière à simplifier l’interface, et regroupé les transitions allant vers le même état lorsque l’option est activée. J’en ai aussi profité pour définir le fond de l’image comme transparent. Il nous faut également mettre à jour les fonctions to_png et to_pdf :

Nous pouvons donc maintenant exporter notre automate complété avec nos nouvelles versions des fonctions :

Voilà qui est donc mieux !

Accessibilité et co-accessibilité

Avant de nous quitter, nous allons nous intéresser au concept d’accessibilité d’un état. Les algorithmes de cette troisième partie sont un poil plus complexes que ce que nous avons vu jusqu’à présent.

Un état est accessible, s’il existe un mot qui permet de l’atteindre. Dans l’automate suivant, l’état 2 n’est pas accessible :

Si tous les états sont accessibles, alors l’automate est accessible. Nous allons donc implémenter la fonction accessible_states qui retourne la liste des états accessibles d’un automate.

Pour ce faire, nous n’allons pas pouvoir simplement itérer parmi tous les états de l’automate, mais nous allons devoir partir de l’état initial, et essayer d’atteindre tout ce qu’on peut à partir des différentes transitions disponibles.

L’algorithme se base sur le principe suivant : si un état Q est accessible, alors ses successeurs sont accessibles. Nous allons donc partir de l’état initial (ici 0) et regarder ses successeurs : 0 et 1. Puis nous allons visiter les successeurs (à l’exception de ceux qui ont déjà été visités) et continuer tant qu’il nous reste des états à visiter.

Lorsque la liste des états à visiter est vide, la liste des états visités correspond aux états accessibles. Pour s’en convaincre, faisons une itération de l’algorithme pour l’automate précédent :

• visité = [], a_visiter = [0].
• On considère l’état 0. successeurs(0) = [0, 1]. On ajoute donc 0 à la liste des états visités et 1 à la liste des états à visiter. => visité = [0], a_visiter = [1]
• On considère l’état 1. successeurs(1) = [3, 4]. => visité = [0, 1], a_visiter = [3, 4]
• On considère l’état 3. successeurs(3) = [3]. => visité = [0, 1, 3], a_visiter = [4]
• On considère l’état 4. successeurs(4) = [0, 3]. => visité = [0, 1, 3, 4], a_visiter = []
• a_visiter est désormais vide, l’algorithme est terminé. 0, 1, 3 et 4 sont accessible, 2 ne l’est pas.

Voici donc pour l’algorithme, nous pouvons donc passer à l’implémentation :

Par confort, ajoutons aussi une fonction permettant de savoir si un automate est accessible (en vérifiant que tous les états sont accessibles) et une seconde pour déterminer si un état particulier est accessible :

Et voilà le travail !

Notez que la notion d’accessibilité d’un automate correspond à la même notion pour les graphes. Dans notre algorithme, nous avons implémenté un parcours en largeur. Cela signifie qu’on va d’abord regarder tous les voisins d’un état, puis leurs voisins etc.

L’autre méthode de parcours d’un graphe est le parcours en profondeur, qui consiste à explorer d’abord le plus loin possible un voisin avant de s’intéresser aux autres voisins. Cela étant, dans notre exemple, les deux parcours donnent le même ordre d’exploration. Notre algorithme correspond à un parcours en largeur, parce qu’on a utilisé la liste to_visit  comme une file, c’est à dire qu’on prend l’élément ajouté le plus récemment en premier (LIFO : Last In First Out). Si on l’implémentait comme une pile (FIFO : First In First Out, par exemple en utilisant to_visit.insert(0,succ) plutôt que to_visit.append(succ)), alors l’algorithme correspondrait à un parcours en profondeur.

Si la notion de parcours en profondeur/largeur est floue, ne vous inquiétez pas, ce n’est de toute façon pas l’objet de cet article. Retournons plutôt à notre implémentation.

Il nous reste à introduire la notion de co-accessibilité, qui est à peu de choses près la même chose. Un état Q est co-accessible s’il existe un mot permettant d’aller vers un état final depuis Q. En fait, c’est pratiquement de l’inverse, il s’agit de savoir si un état final est accessible depuis Q.

L’algorithme est donc sensiblement identique : au lieu d’initialiser notre liste d’états à visiter avec l’état initial, on l’initialise avec l’ensemble des états finaux et au lieu de regarder les successeurs d’un état, on regarde les prédécesseurs :

Nous avons donc terminé pour l’implémentation. Pour tester la co-accessibilité, l’automate abc*_complete fera l’affaire, puisque l’état puits est par définition non co-accessible. Pour l’accessibilité, utilisons le graphe précédent dont le fichier est ci-dessous :

Voyons donc ce que donnent nos nouvelles fonctions :

Avant de nous quitter, sachez qu’un automate qui est à la fois accessible et co-accessible est dit émondé (en anglais trim). La fonction trim ressemblerait donc ça :

Dans ce chapitre, nous avons donc implémenté pas mal de fonctions pour nos automates : successeurs/prédécesseurs, (co)accessibilité et complétude. Un ajout intéressant aurait été la possibilité de rendre un automate accessible, co-accessible ou émondé, mais l’article est déjà bien assez long et cela nous demandera d’ajouter des fonctions de suppression d’états. Nous verrons donc cela une autre fois 🙂 (cela dit, le depôt Github propose peut-être déjà cette fonctionnalité à l’heure où vous lisez ces lignes).

Merci de m’avoir lu jusqu’au bout et je vous dit à très bientôt pour de nouveaux articles.