Abstract FR:

Nous nous intéressons dans ce document aux algorithmes de conversion d'expressions rationnelles en automates, en nous attachant plus particulièrement à la construction de l'automate de Glushkov. Cette construction nous amène à présenter un algorithme original qui fournit une représentation efficace de l'automate de Glushkov d'une expression rationnelle. La structure de données utilisée nous permet notamment de donner un nouvel algorithme de test d'appartenance d'un mot à un langage rationnel. L'étude approfondie de cette représentation nous conduit également à une nouvelle implémentation de l'algorithme de détermination d'un automate. Précisons que chacun des algorithmes présentés fait l'objet d'une étude de complexité.