Automate reconnaissant une expression

Il est fréquent que l'on doive reconnaître dans un texte la présence d'expressions respectant un certain modèle. Le cas typique est la reconnaissance d'une adresse mail : On voudrait reconnaître quelque chose comme :

[des lettres, chiffres et points]@[au moins 3 lettres].[2 ou 3 lettres].

C'est le domaine des expressions régulières. L'expression régulière correspondant à ce qui est écrit au dessus serait :

[A-Za-z0-9.]+@[A-Za-z]{3,}.[A-Za-z]{2,3}

Notre but ici sera de produire un programme capable de reconnaître si une chaîne de caractère respecte une expression régulière très simple.

soit l'expression "(aa*|b)c".

• a signifie : exactement un a
• a* signifie : un nombre quelconque de a
• aa* signifie : un a suivi d'un nombre quelconque de a
• b signifie : exactement un b
• aa*|b signifie : soit un a suivi d'un nombre quelconque de a, soit exactement un b
• "(aa*|b)c" signifie : (soit un a suivi d'un nombre quelconque de a, soit exactement un b) le tout suivi d'exactement un c.

Voici quelques exemples qui valident l'expression ou non :

• "aaaaaaaaac" → oui
• "aaaaaaaaa" → non
• "c" → non
• "ac" → oui
• "bc" → oui
• "aaabc" → non
• "acc" → non
• "bbc" → non

Pour modéliser l'expression, on réalise un automate qui a la forme d'un graphe. Voici le graphe pour le cas précédent.

Le graphe étant défini, on se demande si une certaine chaîne est valide. Par exemple "aac" est-elle valide (la réponse devrait être oui).

1. Au démarrage, on active le nœud initial,
2. on active tous les nœuds qui peuvent être atteints depuis une un nœud actif par des arêtes sans étiquette,
3. s'il reste un caractère à lire dans la chaîne à tester, on le lit. soit car se caractère.
   1. On note tous le nœuds pouvant être atteints depuis un nœud actif, par une arête dont l'étiquette est car.
   2. On désactive tous les nœuds, puis on active tous ceux que l'on vient de noter.
   3. On retourne au point 2.
4. sinon, c'est terminé. Si le nœud final est actif, alors la chaîne testée est valide.
5. À n'importe quel moment, s'il n'y a plus aucun nœud actif, on peut s'arrêter, la chaîne n'est pas valide.

Test de la chaîne "aac".

• A : activation nœud initial,
• B : activation des nœuds pouvant être atteints par des arêtes sans étiquette (gratuitement)
• C : lecture du premier a, on note le(s) nœud(s) pouvant être atteint(s) par une arête étiquetée a,
• D : désactivation de tout, activation des nœuds marqués,
• E : activation des nœuds pouvant être atteints gratuitement
• F : lecture du second a, on note le(s) nœud(s) pouvant être atteint(s),
• G : désactivation de tout, activation des nœuds marqués,
• H : activation des nœuds pouvant être atteints gratuitement
• I : lecture de c, on note le(s) nœud(s) pouvant être atteint(s),
• J : désactivation de tout, activation des nœuds marqués,
• On activera ensuite les nœuds pouvant être atteints gratuitement (ce qui ne changera rien) puis comme il n'y a plus de caractère à lire, on s'arrêtera là.
  Le nœud final étant actif, on conclut que "aac" valide l'expression régulière dont le graphe est une représentation.

On se demande ici comment on peut obtenir le graphe.

La méthode consiste à créer des graphes élémentaires puis à les assemble pour des expressions plus complexe.

Le graphe correspondant à l'expression "a“ est donné ci-dessus.

On a deux expressions "exp1" et exp2" représentée par les graphes G1 (en bleu) et G2 (en violet).

On souhaite obtenir le graphe représentant le choix exp1 OU exp2, que l'on notera "exp1|exp2".

J'ai marqué en pointillé les nœuds initiaux et finaux de G1 et G2 qui cessent de l'être une fois intégrés dans le graphe complet.

On a une expression "exp" associée à son graphe g. On souhaite obtenir le graphe représentant la répétition indéterminée de "exp" ce que l'on notera "exp*".

On a deux expressions "exp1" et exp2" représentée par les graphes G1 (en bleu) et G2 (en violet).

On souhaite obtenir le graphe représentant la suite exp1 exp2 que l'on notera simplement "exp1exp2".