Construction de Glushkov

En informatique théorique et notamment en théorie des automates finis, la construction de Glushkov ou algorithme de Glushkov est un procédé pour construire un automate à partir d'une expression rationnelle. Elle est attribuée à l'informaticien soviétique Victor Glushkov. 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é 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.

Construction

La construction détermine, pour une expression rationnelle $e$ donnée, un automate non déterministe qui reconnaît le langage $L(e)$ dénoté par l'expression. 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 $A$ l'ancien alphabet et $B$ le nouveau.

2a.- Calcul des ensembles $P(e')$, $D(e')$, et $F(e')$, où $e'$ est la version linéarisée de $e$. Le premier, $P(e')$ est l'ensemble des lettres qui peuvent commencer un mot du langage $L(e')$, et le second, $D(e')$, 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 $L(e')$. Ces ensembles se définissent par :

$P(e')=\{a\in B\mid aB^{*}\cap L(e')\neq \emptyset \}$, $D(e')=\{a\in B\mid B^{*}a\cap L(e')\neq \emptyset \}$ et $F(e')=\{u\in B^{2}\mid B^{*}uB^{*}\cap L(e')\neq \emptyset \}$

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 $\Lambda (e')$ qui est composé du seul mot vide si le mot vide est dans $L(e')$, et est l'ensemble vide sinon, formellement

$\Lambda (e')=\{1\}\cap L(e')$, où 1 est le mot vide.

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

$L=(PA^{*}\cap A^{*}D)\setminus A^{*}(A^{2}\setminus F)A^{*}$,

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, union 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

Automate par construction de Gluskkov — version linéaire.

Automate par construction de Gluskkov — version finale.

On considère l'expression rationnelle

$e=(a(ab)^{*})^{*}+(ba)^{*}$.

1.- La version linéarisée est

$e'=(a_{1}(a_{2}b_{3})^{*})^{*}+(b_{4}a_{5})^{*}$.

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

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

$P(e')=\{a_{1},b_{4}\}$, $D(e')=\{a_{1},b_{3},a_{5}\}$ et $F(e')=\{a_{1}a_{2},a_{1}a_{1},a_{2}b_{3},b_{3}a_{1},b_{3}a_{2},b_{4}a_{5},a_{5}b_{4}\}$.

Le mot vide est dans le langage, donc $\Lambda (e')=\{1\}$.

3.- L'automate du langage local

$L'=P'B^{*}\cap B^{*}D'\setminus B^{*}(B^{2}\setminus F')B^{*}$

possède un état initial, noté 1, et un état pour chacune des cinq lettres de l'alphabet $B=\{a_{1},a_{2},b_{3},b_{4},a_{5}\}$. Il y a une transition de 1 vers les deux états dans $P'$, une transition de $a$ vers $b$ si $ab$ est dans $F'$, et les trois états de $D'$ 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 $L(e)$ en supprimant les indices.

Calcul des ensembles de lettres

Le calcul des ensembles $P$, $D$, $F$ et $\Lambda$ 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 $+,\cdot ,*$.

1.- Pour $\Lambda$, on a

$\Lambda (0)=\emptyset ,\Lambda (1)=\{1\}$, et $\Lambda (a)=\emptyset$ pour toute lettre $a$,

puis

$\Lambda (e+f)=\Lambda (e)\cup \Lambda (f),\Lambda (e\cdot f)=\Lambda (e)\cdot \Lambda (f)$ et enfin $\Lambda (e^{*})=\{1\}$

2.- Pour $P$, on a

$P(0)=P(1)=\emptyset$ et $P(a)=\{a\}$ pour tout lettre $a$,

puis

$P(e+f)=P(e)\cup P(f),P(e\cdot f)=P(e)\cup \Lambda (e)P(f)$ et enfin $P(e^{*})=P(e)$.

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

$D(e\cdot f)=D(f)\cup D(e)\Lambda (f)$.

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

$F(0)=F(1)=F(a)=\emptyset$ pour toute lettre $a$,

puis

$F(e+f)=F(e)+F(f),F(e\cdot f)=F(e)\cup F(f)\cup D(e)P(f)$ et enfin $F(e^{*})=F(e)\cup D(e)P(e)$.

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

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

Propriétés

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é 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.

Complexité en temps (par étapes)

On note n le nombre de caractères présents dans l’expression rationnelle définissant le langage.

NB : on entend par caractère toute apparition d’une lettre ou d’un symbole + , . , * , ( , )

Exemple : $e=(a(ab)^{*})^{*}+(ba)^{*}$ contient 18 caractères.

1- Linéarisation de l’expression (passage de e à e’)

(Exemple : $e=(a(ab)^{*})^{*}+(ba)^{*}$ devient $e'=(a_{1}(a_{2}b_{3})^{*})^{*}+(b_{4}a_{5})^{*})$ Complexité : $O(n)$

2- Construction des ensembles définissant le langage local (P(e’), D(e’), et F(e’) déjà définis sur Wikipédia)

Peut se faire en un seul parcours, en effectuant un nombre fini de tests en fonction du symbole rencontré (ce sont bien sûr les symboles qui définissent)

Donc, on obtient une complexité en $O(n)$.

3- Construction de l’automate à l’aide des ensembles

Il s’agit d’un parcours de F(e’), commençant par un facteur dont la lettre de gauche est dans P(e’). Ensuite, on cherche un autre facteur commençant par la lettre qui termine le premier, et ainsi de suite...

(Exemple : Si on commence, par $a_{1}$, on lit d’abord $a_{1}a_{2}$, puis $a_{2}b_{3}$. Et comme $b_{3}$ est dans D(e’), on s’arrête)

En effet, le parcours s’arrête lorsqu’on aboutit à un état terminal (un élément de D(e’)).

Chaque chemin ainsi construit a donc une complexité en $O(n)$, mais comme il peut y avoir dans le pire des cas n chemins, on obtient une complexité en $O(n^{2})$.

4- Suppression des indices en $O(n)$.

Preuve de terminaison (par étapes)

Il est clair que les étapes 1 et 4 se font en temps fini.

2- Il y a un nombre fini de caractères dans une expression rationnelle, donc un nombre fini de facteurs de longueur 1 et 2. Donc les ensembles P(e’), D(e’), et F(e’) sont finis.

3- On a évoqué la répartition de la construction de l’automate en chemins. Il suffit alors de montrer qu’un chemin est fini pour conclure.

On choisit un élément de P(e’), et on construit un chemin comme expliqué précédemment.

Si l’une des lettres réapparaît dans le chemin, alors on a construit un cycle, donc on peut terminer le chemin maintenant, sans changer l’automate.

Sinon, alors on visite toutes les lettres de l’expression rationnelle, et comme elles sont en nombre fini, on arrive obligatoirement sur un élément de D(e’) en temps fini, donc le chemin est construit.

Donc l’algorithme termine. L’automate ainsi construit est non déterministe, et comporte autant d’états qu’il y a de lettres dans l’expression linéarisée e’.

Applications et expressions déterministes

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.

Comparaison avec l'algorithme de Thompson

	Glushkov	Thompson
Travail préalable	Linéarisation de e, et construction des ensembles P(e’), D(e’), F(e’) en $O(n)$	Aucun
Construction d’automate	Automate directement construit par parcours des ensembles en $O(n^{2})$	Automate directement construit en $O(n)$
Travail après construction	Aucun	Retirer les ε-transitions

Bibliographie

• (en) Gérard Berry et Ravi Sethi, « From regular expressions to deterministic automata », Theoretical Computer Science, vol. 48,‎ 1986, p. 117-126 (ISSN 0304-3975).
• (en) Victor M. Glushkov, « The abstract theory of automata », Russian Mathematical Surveys, vol. 16,‎ 1961, 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,‎ 1996, p. 439–446.
• (en) Jean-Éric Pin, « Finite automata », dans Jean-Éric Pin (éditeur), Handbook of Automata Theory, 2010
• Olivier Carton, Langages formels, calculabilité et complexité, 2008 [détail de l’édition] (lire en ligne)
• Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, 2003, 816 p. (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, n^o 1,‎ 1997, p. 177–203 (lire en ligne [PDF])