MP1/MP*: Option Informatique
Devoir à rendre après les vacances de Noël
Langages locaux, automates locaux et algorithme de McNaughton, Yamada et Glushkov



Présentation

Le théorème de Kleene affirme l'équivalence entre reconnaissabilité et rationnalité. On connaît des preuves constructives de ce théorème: une telle preuve fournit un algorithme associant à un automate A une expression rationnelle e qui décrit le langage reconnu par A, ou, en sens inverse, associant à une expression rationnelle e un automate A qui reconnaît le langage décrit par e.

C'est à cette deuxième construction, d'utilisation fréquente, que nous nous intéresserons. La méthode la plus connue, et aussi la plus facile à expliquer, repose sur l'utilisation des automates de Thompson. Nous étudierons ici une autre méthode, connue sous le nom d'algorithme de Berry-Sethi (mais qui, en fait, a été exposée en premier par Glushkov).

L'énoncé s'inspire très largement de l'article paru dans le numéro 155 de la revue Theoretical Computer Science et cosigné par Jean Berstel et Jean-Éric Pin.