Présentation

Il est bien connu que le coût de la déterminisation d'un automate fini peut être exponentiel; ainsi, le langage décrit par l'expression rationnelle (a+b)*a(a+b)^n est reconnu par un automate non déterministe à n+1 états, mais ne peut être reconnu par un automate déterministe ayant moins de 2^n états.

Kai Salomaa et Sheng Yu se sont posé la question suivante: que se passe-t-il lorsque l'on veut déterminiser un automate fini reconnaissant un langage fini? Ils sont montré qu'ici encore, le coût pouvait être exponentiel, et ont donné un majorant exact. Très précisément, ils ont prouvé que si un langage fini était reconnu par un automate fini à n états, alors il était aussi reconnu par un automate déterministe ayant au plus 2^(p+1)-1 états si n=2p, à 2^(p+1)+2^p-1 états si n=2p+1. Ils ont donné des exemples pour lesquels ces bornes étaient atteintes.

Ce texte reprend pour l'essentiel leurs mode d'exposition; il est abordable par les étudiants de deuxième année qui ont suivi le cours sur les automates finis.

Ce sujet a été traité par les étudiant(e)s au cours des vacances de Noël 1998.