Construction de Glushkov

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En informatique théorique et notamment en théorie des automates finis, la construction de Glushkov ou algorithme de Glushkov, attribuée à l'informaticien soviétique Victor Glushkov[1], est un procédé qui permet de construire un automate à partir d'une expression rationnelle. L'automate obtenu est non déterministe, et de même taille (comptée en nombre d'états) que la taille (comptée en nombre de symboles) de l'expression rationnelle. Il a été observé[1] que l'automate de Glushkov est le même que l'automate obtenu en supprimant les ε-transitions de l'automate obtenu par la méthode de Thompson.

La construction de Glushkov est aussi appelée algorithme de Berry-Sethi, d'après Gérard Berry et Ravi Sethi qui ont travaillé sur cette construction[2].

Construction[modifier | modifier le code]

La construction détermine, pour une expression rationnelle donnée, un automate non déterministe qui reconnaît le langage dénoté par l'expression[3]. La construction est en quatre phases :

1.- Linéarisation de l'expression. Les symboles de l'alphabet figurant dans l'expression sont renommés de sorte que chaque symbole n'y figure qu'une fois. Notons l'ancien et le nouvel alphabet.

2a.- Calcul des ensembles , , et , où est la version linéarisée de . Le premier, est l'ensemble des lettres qui peuvent commencer un mot du langage , et le second, , est celui des lettres qui peuvent finir un mot. Le dernier est l'ensemble des couples de lettres (facteurs de longueur 2) qui peuvent figurer dans les mots de . Ces ensembles se définissent par :

, et

Ils sont calculés par récurrence sur la structure de l'expression, comme expliqué plus bas, mais ils dépendent du langage et non de l’expression.

2b.- Calcul de l'ensemble qui est composé du seul mot vide si le mot vide est dans , et est l'ensemble vide sinon, formellement

, où 1 est le mot vide.

3.- Calcul de l’automate du langage local défini par , , et et . Par définition, le langage local défini par des ensembles , , et est l'ensemble des mots qui débutent par une des lettres de , finissent par une des lettres de , et dont tous les facteurs de longueur 2 sont dans ; en d'autres termes, c'est le langage :

,

augmenté éventuellement du mot vide.

Le calcul de l'automate pour le langage local dénoté par l'expression linéarisée est, à proprement parler, la construction de Glushkov. La construction de l'automate est possible grâce au construction classique : concaténation, intersection et itération d'automate.

4.- Effacement de la linéarisation, par identification des lettres qui avaient reçus des noms différents dans la première étape.

Exemple[modifier | modifier le code]

Automate par construction de Gluskkov — version linéaire.
Automate par construction de Gluskkov — version finale.

On considère[3] l'expression rationnelle

.

1.- La version linéarisée est

.

On a distingué ici les lettres simplement en les indiçant par leur position dans l’expression.

2.- Les ensembles , , et des premières et dernières lettres, et des facteurs de longueur 2 pour l'expression linéarisée sont respectivement

, et .

Le mot vide est dans le langage, donc .

3.- L'automate du langage local

possède un état initial, noté 1, et un état pour chacune des cinq lettres de l'alphabet . Il y a une transition de 1 vers les deux états dans , une transition de vers si est dans , et les trois états de sont terminaux ainsi que l'état 1. Toutes les transitions portent comme étiquette la lettre qui est l'état d'arrivée (et donc toutes les transitions arrivant en un état donnés ont la même étiquette, à savoir le nom de cet état).

4.- Obtention de l’automate pour en supprimant les indices.

Calcul des ensembles de lettres[modifier | modifier le code]

Le calcul des ensembles , , et se fait par récurrence sur la structure de l’expression. Il faut donc donner les valeurs pour 0, 1 (expressions de l'ensemble vide et du mot vide), des lettres, et le résultat des opérations .

1.- Pour , on a

, et pour toute lettre ,

puis

et enfin

2.- Pour , on a

et pour tout lettre ,

puis

et enfin .

Les mêmes formules valent pour , sauf pour le produit, où on a

.

3.- Pour les facteurs de longueur 2, on a

pour toute lettre ,

puis

et enfin .

Les opérations coûteuses sont les produits d'ensembles pour le calcul de .

On trouve souvent les notations First, Last, Follow ou Prem, Der, Suiv pour , , et respectivement.

Propriétés[modifier | modifier le code]

L'automate obtenu est non déterministe, et de même taille (comptée en nombre d'états) que la taille (comptée en nombre de symboles) de l'expression rationnelle. Il a été observé[1] que l'automate de Glushkov est le même que l'automate obtenu en supprimant les ε-transitions de l'automate obtenu par la méthode de Thompson.

Applications et expressions déterministes[modifier | modifier le code]

Le calcul de l'automate à partir de l'expression intervient dans de nombreuses circonstances, et a été utilisé de manière systématique dans des fonctions de recherche de motifs dans les textes, comme la commande grep de Unix. Les spécifications des formats XML font appel aussi à ces constructions; pour les rendre efficaces, des expressions régulières d'un type particulier appelées expressions déterministes ont été étudiées[4],[1].

Notes et références[modifier | modifier le code]

  1. a, b, c et d Sakarovitch 2003, p. 215.
  2. Berry et Sethi 1986.
  3. a et b Pin 2010.
  4. Anne Brüggemann-Klein, « Regular Expressions into Finite Automata », Theoretical Computer Science, vol. 120, no 2,‎ , p. 197-213 (DOI 10.1016/0304-3975(93)90287-4).

Bibliographie[modifier | modifier le code]

  • (en) Gérard Berry et Ravi Sethi, « From regular expressions to deterministic automata », Theoretical Computer Science, vol. 48,‎ , p. 117-126 (ISSN 0304-3975).
  • (en) Victor M. Glushkov, « The abstract theory of automata », Russian Mathematical Surveys, vol. 16,‎ , p. 1-53 (ISSN 0036-0279).
  • (en) Jean Berstel et Jean-Éric Pin, « Local languages and the Berry-Sethi algorithm », Theoretical Computer Science, vol. 155,‎ , p. 439–446.
  • (en) Jean-Éric Pin, « Finite automata », dans Jean-Éric Pin (éditeur), Handbook of Automata Theory,
  • Olivier Carton, Langages formels, calculabilité et complexité, [détail de l’édition] (lire en ligne)
  • Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, (ISBN 978-2-7117-4807-5) — Traduction anglaise avec corrections : Elements of Automata Theory, Cambridge University Press 2009 (ISBN 9780521844253).
  • Djelloul Ziadi, Jean-Luc Ponty et Jean-Marc Champarnaud, « Passage d’une expression rationnelle à un automate fini non déterministe », Bulletin of the Belgian Mathematical Society Simon Stevin, vol. 4, no 1,‎ , p. 177–203 (lire en ligne [PDF])