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.