Les automates – Négation et produit

Bonjour tout le monde ! L’article d’aujourd’hui est le quatrième de la série sur les automates finis et sera consacré à la négation et au produit d’AFD.

La négation d’un automate

Pour introduire la négation d’automate, penchons nous sur le problème suivant : donnez un automate, sur l’alphabet Σ = {a, b}, qui reconnait les mots contenant la séquence aaba.

Comme vous l’avez surement remarqué, il s’agit à nouveau de notre automate *aaba* que nous nous trimbalons depuis le premier chapitre.

Pour reprendre un peu de terminologie, un automate reconnait un langage, c’est-à-dire un ensemble de mot (qui peut être fini ou non) sur un alphabet donné. On note L(A) le langage reconnu par un automate A et de la même façon, on note A(L) l’automate qui reconnait un langage L. Nous allons noter L₁ le langage correspondant aux mots contenant la séquence “aaba”, notre automate *aaba* est donc A(L₁).

Si maintenant je vous demande de trouver un automate qui reconnait le langage L₂, correspondant aux mots ne contenant pas la séquence aaba ? Si Σ^* est l’ensemble des mots possibles sur l’alphabet Σ, on peut remarquer que L₂ = Σ^* \ L₁. En d’autres termes, tous les mots n’appartenant pas à L₁, sont dans , et inversement. On peut aussi dire que L₁ ∪ L₂ = Σ^* : l’union des deux langages donne tous les mots possible sur l’alphabet Σ.

Dans ce cas là, on dit que est L₂ le langage complémentaire de L₁. On notera L^c le langage complémentaire d’un langage L, et donc L₂ = L_1^c.

Pourquoi est-ce intéressant ? Et bien parce-que trouver un automate reconnaissant L^c est très facile si on connait déjà A(L). A(L^c) est la négation de A(L).

Bien sûr, il est possible de trouver l’automate reconnaissant les mots ne contenant pas la séquence “aaba” sans avoir recours à la négation de notre automate *aaba*, mais comme vous allez le voir, la négation d’un automate est on ne peut plus simple.

La négation d’un automate ne peut se faire que sur un AFD complet. L’algorithme de négation consiste uniquement a inverser les états accepteurs et non accepteurs :

Puisque nous stockons les états finaux dans une liste, l’idée est de remplacer cette liste d’états finaux par tous les états n’étant pas finaux dans l’automate d’origine.

Nous pouvons maintenant tester notre code est obtenir un automate qui reconnait les mots ne contenant pas la séquence aaba : 

Mission accomplie !

Le produit de deux automates

Nous allons maintenant attaquer la deuxième partie de cet article : le produit d’automates.

Intéressons nous au problème suivant : donnez l’automate reconnaissant les mots qui contiennent un nombre pair de ‘a’ ET qui ne contiennent pas deux ‘b’ à la suite.

S’il est possible de trouver cet automate par intuition, on se rends très vite compte que le langage reconnu par cet automate, que nous appellerons L, est en fait l’intersection de deux langages :

• L = L₁ ∩ L₂,
• L₁ = les mots contenant un nombre pair de ‘a’.
• L₂ = les mots qui ne contiennent pas deux ‘b’ successifs.

L’intersection de deux langages, c’est à dire un langage contenant tous les mots étant appartenant aux deux langages en même temps, revient à calculer le produit des automates verifiant chaque langage. Ainsi, A(L₁ ∩ L₂) = A(L₁) X A(L₂).

Pour un problème comme celui-ci, nous allons donc construire un automate reconnaissant L₁ et L₂, puis appliquer l’algorithme de produit d’automate. Commencons par construire les automates A(L₁) et A(L₂). L’automate reconnaissant L₁ est très simple à construire :

Le fichier .dfa associé :

L’automate A(L₂), est lui aussi très simple. Je vous propose de le construire directement, mais on aurait aussi pu décider de calculer la négation de l’automate reconnaissant les mots contenant la séquence ‘bb’ :

Nous allons maintenant nous intéresser à calculer le produit des automates pair_a et not_*bb*, de manière à obtenir l’automate reconnaissant le langage L.

L’algorithme

L’algorithme du produit d’automates se base sur le concept de super-état.

On construit le super-état à partir des états initiaux de chaque automate. Ici, on va créer le super-état {0, 0}. Pour qu’un super-état soit accepteur, il faut que les deux états correspondant soient accepteurs. Puisque l’état 0 de l’automate A(L₁) et l’état 0 de A(L₂) sont accepteur, alors {0, 0} est accepteur.

Ensuite, nous allons créer les transitions pour notre super-état. Pour cela, il suffit de regarder les transitions des états originaux :

• 0 de A(L₁) a une transition vers 1 en a. 0 de  A(L₂) a une transition vers 0 en a. Nous allons donc créer une transition en a de {0, 0} vers un nouveau super-état {1, 0}.
• De la même manière, pour b, l’état de destination est {0, 1}. Puis que les deux états concernés sont accepteurs, {0, 1} est lui aussi accepteur.

Et on va continuer ainsi pour tous les super-états que l’ont crée. Le produit de deux automates ayant respectivement n et m états donnera un automate comportant au maximum n*m états. Cela étant, il peut arriver qu’on obtienne moins d’états.

Notre super-état {1, 0} a donc pour successeurs {0, 0} en a et {1, 1} en b. Puisque nous avons déjà créé {0, 0}, il faut bien entendu réutiliser ce super-état :

{0, 1} a pour successeurs {1, 0} en a et {0, 2} en b :

{1, 1} a pour successeurs {0, 0} en a et {1, 2} en b :

{0, 2} a pour successeurs lui-même en a et {1, 2} en b :

{1, 2} a pour successeurs {0, 2} en a et {1, 2} en b :

Et voilà ! L’automate obtenu est le produit des automates pair_a et not_*bb*.

L’algorithme est un peu plus complexe que ce que nous avons vu auparavant, mais il est finalement assez simple à appréhender. Avant de passer à l’implémentation, je vous propose deux petites précisions :

Que se passe-t-il si un des deux états d’origine n’a pas de transition pour un symbole donné ? Si tel est le cas, on ajoute pas de transition au super-état.

Peut-on faire le produit d’automates ayant des alphabets différents ? Tout à fait ! En fait, si les alphabets diffèrent, l’automate produit utilisera l’union des deux alphabets. Par exemple, si A1 est défini sur l’alphabet {a, b} et A2 sur l’aphabet {a, c}, alors A1 X A2 aura pour alphabet {a, b, c}. A nouveau, si des transitions sont manquantes, on ignore simplement la transition pour le super-état.

Notez que si les alphabets sont disjoins, par exemple {a, b} et {c, d}, on sait d’avance que le produit reconnaîtra soit le mot vide (si les deux automates l’acceptent), soit le langage vide.

Implémentation

Nous pouvons maintenant passer à l’implémentation de l’algorithme. De la même manière que pour l’accessibilité, nous allons maintenir une liste des super-état qui n’ont pas encore été traité (entendez par là qu’ils ont été crée mais dont les transitions n’ont pas été calculées). Nous ajouterons dans cette liste des triplets contenant le super-état et les deux états d’origine correspondants.

Ensuite, pour chaque super-état à traiter, on calcule les super-états successeurs pour chaque symbole et on les ajoute à la liste des états à traiter si-nécessaire. Si une des transitions des états d’origine est absente, on ignore la transition du super-état pour ce symbole.

J’ai utilisé une fonction interne  get_superstate permettant de créer le nom d’un super-état à partir des états d’origine et qui se charge également d’ajouter le super-état à la liste des états à traiter si celui-ci n’existait pas. Cette fonction en profite pour calculer si le super-état est final ou non.

De plus, il ne faut pas oublier de calculer l’union des alphabets pour l’automate produit. Etant donné que les automates d’entrée ne sont pas modifiés, il n’est pas nécessaire d’en faire une copie. Voici donc le code final :

Testons notre nouvelle fonction à l’aide des automates pair_a et not_*bb* :

Et voilà ! L’automate produit est conforme à ce que nous attendions.

Avant de nous quitter, on pourrait aussi s’interroger sur un problème un peu plus complexe :donnez l’automate reconnaissant les mots qui contiennent un nombre pair de ‘a’ ET qui ne contiennent pas deux ‘b’ à la suite ET qui ne contient pas la séquence ‘aaba’.

Cet automate est le produit de trois automates : pair_a, not_*bb* et la négation de aaba. Pour effectuer le produit de trois automates, il nous suffit de faire le produit de deux automates et d’en faire le produit avec le troisième. Nous allons donc faire le produit de pair_a_X_not_*bb* avec *aaba*_neg :

Le résultat est très gros, je vous laisse imaginer le temps que ça peut prendre si on avait voulu appliquer l’algorithme à la main et la difficulté que ça peut être d’essayer de construire de tels automates sans utiliser la négation et le produit d’automates plus petits.

Cependant on peut maintenant se poser une question. N’y aurait-il pas moyen d’avoir un automate équivalent plus simple ? Et bien surement, et ce sera pour le prochain chapitre. A très bientôt !