Opérations sur les automates lexicaux

Opérations sur les automates lexicaux

Grâce à cette représentation structurée des masques lexicaux permettant d’implémenter des opérations ensemblistes sur ces objets, nous sommes maintenant en mesure d’adapter les algorithmes classiques sur les automates finis (tels que définis dans [Hopcroft et Ullman, 1979] par exemple) de manière à ce qu’ils aient un comportement correct sur les automates lexicaux. Les modifications apportées à ces algorithmes consistent essentiellement à découper les transitions afin que les ensembles décrits dans leurs étiquettes soient deux à deux soit disjoints, soit égaux.

Nous procédons à ce découpage sur les transitions sortantes des états considérés à chaque étape du calcul de manière à ce que deux masques distincts susceptibles d’être comparés ont toujours une intersection vide. Cette propriété est suffisante à la correction de la plupart des algorithmes et nous avons pu ainsi implémenter le calcul de la déterminisation, la minimisation ou de l’intersection pour les automates lexicaux. La figure 2.10, par exemple, présente l’automate de la figure 2.2 (page 15) correctement déterminisé. 

Le calcul de la complémentation d’un automate lexical est différent puisqu’il consiste à inverser la terminalité des états de l’automate après l’avoir rendu complet. Pour ce faire nous rajoutons, pour chaque état, de nouvelles transitions sortantes dirigées vers un état puits et étiquetées par l’ensemble du lexique qui n’est pas décrit par les transitions déjà existantes, ensemble qu’il nous est maintenant possible de calculer.

Notons que le calcul de l’union ou de la concaténation de deux automates lexicaux ou encore le calcul de l’étoile de Kleen d’un automate lexical ne nécessitent pas de manipulation particulière sur les transitions. Dans cette section, après avoir donné une définition formelle des automates que nous manipulons,

nous présentons notre algorithme de découpage des transitions, qui prend en entrée un ensemble de transitions et produit en sortie un ensemble équivalent tel que les masques qui étiquettent ces transitions soient deux à deux disjoints ou égaux. Nous illustrons ensuite l’intérêt d’un tel découpage en détaillant notre algorithme qui implémente la déterminisation d’un automate lexical. Nous avons implémenté sur le même principe l’opération d’intersection de deux automates lexicaux. 

Définition formelle

Étant donné un jeu d’étiquettes, nous définissons formellement un automate lexical non déterministe comme un quintuplet A = (Lex, Q, I, F, ∆) où : – Lex est l’ensemble des masques lexicaux définis sur le jeu d’étiquettes  utilisé ; – Q est un ensemble fini d’état ; – I ⊆ Q est l’ensemble des états initiaux ; – F ⊆ Q est l’ensemble des états finaux ; – ∆ ⊆ Q × Lex × Q est un ensemble de transitions lexicales.

Une transition lexicale est définie comme un triplet t = (qo, m, qd) où – qo est l’état d’origine, – m est le masque lexical qui étiquette cette transition et – qd l’état de destination. Étant donnée une transition lexicale t, on notera orig(t), label(t) et dest(t) ces trois éléments respectifs. De la même manière,

nous définissons un automate lexical déterministe comme un quintuplet A = (Lex, Q, i, F, δ) où : – Lex est l’ensemble des masques lexicaux ; – Q est un ensemble fini d’état ; – i ∈ Q est l’état initial ; – F ⊆ Q est l’ensemble des états finaux ; – δ : Q × Lex 7→ Q est la fonction de transition ; – Pour tout q ∈ Q et pour tout m1, m2 ∈ Lex, si δ(q, m1) et δ(q, m2) sont définis, alors soit m1 ∧ m2 = ∅ soit m1 = m2.