Problème de la hauteur d'étoile

Le problème de la hauteur d'étoile, en théorie des langages formels, est le problème qui consiste à déterminer la hauteur d'étoile d'un langage rationnel, c'est-à-dire le nombre minimal d'étoiles de Kleene imbriquées nécessaires dans une expression rationnelle pour qu'elle puisse dénoter ce langage. Il existe des langages rationnels de hauteur d'étoile arbitrairement grande, mais la détermination de la hauteur d'étoile d'un langage rationnel, tout en étant décidable, est très difficile. vignette|Exemple d'une expression rationnelle de hauteur d'étoile égale à 2. La hauteur d'étoile d'une expression rationnelle est le nombre maximum d'étoiles emboîtées nécessaires pour la décrire. Par exemple, la hauteur d'étoile de l'expression rationnelle est égale à . Toutefois, la hauteur d'étoile d'une expression rationnelle n'est pas nécessairement le nombre d'étoile apparaissant dans l'expression. Par exemple, la hauteur d'étoile de l'expression rationnelle est égale à alors que le nombre d'étoiles est . Plus formellement, on définit la hauteur d'étoile d'une expression rationnelle comme étant le nombre défini récursivement comme suit : pour toute lettre On souhaite étendre cette définition aux langages rationnels. Cependant, il est à noter que deux expressions rationnelles différentes peuvent avoir une hauteur d'étoile différente tout en décrivant le même langage. Par exemple, on a : mais . On ne peut donc pas définir la hauteur d'étoile d'un langage rationnel comme étant la hauteur d'étoile d'une expression rationnelle arbitraire le décrivant. C'est pourquoi la hauteur d'étoile d'un langage rationnel est défini comme étant le minimum des hauteurs d'étoile des expressions dénotant ce langage, c'est-à-dire : On peut, par exemple, se servir de cette notion pour caractériser un certain type de langage : un langage rationnel est fini (i.e. ne possède qu'un nombre fini de mots) si et seulement si sa hauteur d'étoile est nulle. Le problème de la hauteur d'étoile concerne les langages rationnels, il peut être utile d'étudier la manière de le traiter avec des automates finis.