Conversions effectives entre expressions régulières et automates finis

Abstract

Ce mémoire s'articule autour de quatre chapitres. Le premier constitue un rappel sur les expressions régulières et les automates. Il contient quelques définitions essentielles et une introduction au théorème de Kleene. Le deuxième chapitre présente la méthode des dérivées et des dérivées partielles pour passer d'une expression régulière à un automate fini. Le troisième chapitre décrit la méthode de suppression d'états pour passer d'un automate à une expression régulière. De plus, on présente également deux heuristiques pour tenter d'obtenir une expression plus courte. Il s'agit de l'heuristique des ponts par Han et Wood et de l'heuristique des poids par Delgado et Morais. Enfin, le quatrième et dernier chapitre est une succincte explication de l'implémentation réalisée. On y présente les choix de représentations et quelques commentaires sur l'utilisation du code.