Construction de Glushkov

Carte Commune · n° 414292

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.

Lire sur Wikipédia