-
Minimisation d'automates de couverture d'un langage fini
-
Tuteurs :
Marie-Pierre.Beal@univ-mlv.fr
Langage de programmation : Java, C++, C (Java de préférence)
Environnement de développement : UNIX ou Linux
Domaine : Algorithmique sur les automates
Pré-requis : Cours sur les automates et cours d'algorithmique de licence.
-
Sujet
-
Le projet consiste à implémenter une méthode de minimisation d'un
automate fini déterministe couvrant un ensemble fini de mots L. Si l est la longueur
du plus grand mot de L, un tel automate
reconnaît les mots de L plus éventuellement d'autres mots de longueur supérieure à l.
L'intérêt est qu'un tel automate peut être beaucoup plus petit que
l'automate minimal classique
et permet de reconnaître si un mot est dans le langage de la façon
suivante.
Si le mot a une longueur strictement supérieure à l, il est rejeté.
Sinon, on le fait passer dans l'automate de couverture. Si on arrive
sur un état terminal, il est accepté, sinon il est rejeté.
Des méthodes à la Nérode ou Hopcroft permettent de minimiser un tel
automate.
On demande d'implémenter une méthode à la Hopcroft (en n log n)
et le détail de l'algorithme sera fourni à ceux qui sont intéressés
par se sujet, qui est typiquement un sujet d'algorithmique sur les graphes.
|