Projets tutorés
licence d'informatique

Minimisation de transducteurs

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 de transducteurs. Les transducteurs sont utilisés en traitement automatique de la langue, en arithmétique des ordinateurs, en codage. La minimisation permet de réduire leur taille sans perte de leur potentiel de calcul.
Les transducteurs sont des automates finis dont les étiquettes sont constituées d'un mot d'entrée et d'un mot de sortie. On suppose que les entrées sont en fait des lettres et que l'automate d'entrée est un automate déterministe. Les étiquettes de sorties sont par contre des mots. L'algorithme comprend deux étapes.

• La première étape consiste à calculer l'automate préfixe de l'automate fini constitué par les étiquettes de sortie. Cette transformation consiste à pousser le plus possible les lettres des états terminaux vers les états initiaux sans changer ni graphe de l'automate ni le langage reconnu. L'algorithme comprend une boucle qui contient essentiellement deux explorations en profondeur à chaque étape. Cet algorithme est décrit dans Computing the prefix of an automaton.
• La deuxième étape consiste en une minimisation classique d'un automate fini. On implémentera une des méthodes étudiées dans le cours Automates du premier semestre.

Les deux étapes devront être indépendantes.
Il faudra réfléchir soigneusement à l'implémentation des automates et des transducteurs.
L'architecture de l'implantation comprendra deux éléments principaux :

• un module d'interface
• un module de minimisation

Enfin, une phase du projet sera consacrée à des tests sur la taille des transducteurs obtenus et la vitesse de minimisation.

Documents

• Computing the prefix of an automaton.