Problème de la hauteur d'étoile

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 ${\displaystyle (a^{\star }+b)^{\star }}$ est égale à ${\displaystyle 2}$. 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 ${\displaystyle (a^{\star }+b)^{\star }c^{\star }}$ est égale à ${\displaystyle 2}$ alors que le nombre d'étoiles est ${\displaystyle 3}$.

Plus formellement, on définit la hauteur d'étoile d'une expression rationnelle ${\displaystyle e}$ comme étant le nombre ${\displaystyle h(e)}$ défini récursivement comme suit :

1. ${\displaystyle h(a)=0\,}$ pour toute lettre ${\displaystyle a}$
2. ${\displaystyle h(e+f)=h(e\cdot f)=\max\{h(e),h(f)\}}$
3. ${\displaystyle h(e^{\star })=1+h(e)}$.

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 : ${\displaystyle (a+b)^{\star }=(a^{\star }b)^{\star }a^{\star }}$ mais ${\displaystyle h((a+b)^{\star })=1\neq 2=h((a^{\star }b)^{\star }a^{\star })}$. 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 ${\displaystyle X}$ est défini comme étant le minimum des hauteurs d'étoile des expressions dénotant ce langage, c'est-à-dire :

${\displaystyle h(X)=\min\{h(e)\mid L(e)=X\}}$.

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.

La notion de rang cyclique[1] d'un automate[2] permet de justifier plus précisément le lien qu'il y a entre le problème de la hauteur d'étoile d'un langage et le nombre de cycles imbriqués des automates acceptant celui-ci. Les notions s'appliquent à des automates déterministes ou non, et sont en fait des notions de graphes.

On définit la notion de rang pour une composante fortement connexe d'un graphe comme suit. Le rang est égal à :

• 0 si la composante possède un unique sommet n'a pas de boucle autour de ce sommet ;
• 1 s'il existe un sommet par lequel passent tous les cycles de cette composante
• k (avec k ≥ 2) s'il existe un sommet tel que le graphe obtenu en supprimant ce sommet et les arcs qui lui sont adjacents (c'est-à-dire dont ce sommet est l’origine ou la destination) contient un cycle de rang k−1 (et éventuellement des cycles de rang inférieur), et si le graphe obtenu en supprimant tout autre sommet que celui du cycle initial contient au moins un cycle de rang supérieur où égal k-1. En d'autres termes, c'est 1+ le plus petit des rangs obtenus en supprimant un sommet.

Le rang cyclique d'un automate est défini comme suit :

• Si l'automate est acyclique, son rang cyclique est nul (dans ce cas, le langage reconnu est fini) ;
• sinon, il est égal au maximum du rang de ses composantes connexes (qui existent car l'automate possède au moins un cycle).

L'automate de la Fig. 3 est de rang cyclique 0 car il est acyclique (le langage qu'il reconnaît est réduit au mot a et est donc fini). Un exemple d'automate de rang cyclique 1 est celui de la Fig. 1 car tous les cycles de celui-ci passent par le sommet 1. Enfin, l'automate représenté sur la Fig. 2 est, lui, de rang cyclique 2 : si on supprime l’un des sommets, le graphe résultant est de rang 1.

L'utilisation du rang cyclique d'un automate se justifie ici grâce au théorème suivant qui exprime la hauteur d'étoile d'un langage en fonction du rang cyclique des automates qui le reconnaissent.

Le théorème de Eggan[3] démontre donc qu'en connaissant tous les automates finis d'un langage, on est capable d'en déduire sa hauteur d'étoile. Cependant, comme existe plusieurs automates finis reconnaissant un même langage, le minimum à calculer dans le théorème impose que l’on ne peut pas utiliser seulement un automate particulier. De plus, la hauteur d'étoile n'est pas une propriété syntaxique (sinon un langage et son complément auraient la même hauteur, ce qui n'est pas le cas : il suffit de prendre le langage de tous les mots et son complémentaire, le langage vide), et donc on ne peut pas se contenter d'étudier son automate minimal. Toutefois, et sous certaines conditions, on peut quand même utiliser un automate minimal. Cela fait l'objet du théorème[4] suivant :

Exemple

Mots avec un nombre pair de ${\displaystyle b}$.

Soit ${\displaystyle X}$ l'ensemble des mots sur l'alphabet ${\displaystyle \{a,b\}}$ qui contiennent un nombre pair de ${\displaystyle b}$. L'automate déterministe minimal reconnaissant ${\displaystyle X}$ est donné dans la figure ci-contre. Les lettres réalisent des permutations des états de l’automate, donc le monoïde syntaxique est un groupe. Par le théorème, on en déduit que la hauteur d'étoile de ${\displaystyle X}$ est égal au rang cyclique de cet automate, ici 2. Un expression régulière pour le langage est ${\displaystyle (a^{*}+ba^{*}b)^{*}}$.

Ces théorèmes montrent que le problème de la hauteur d'étoile peut se réduire à un problème de complexité dans un automate reflété par le nombre de circuits imbriqués. Cette réduction du problème sur un langage à un problème sur les automates s'avère très utile pour montre la décidabilité du problème de la hauteur d'étoile d'un langage.

Une première réponse a été donnée par Eggan lui-même. Les premiers des langages donnés par Eggan[3] sont décrits par les expressions rationnelles suivantes :

${\displaystyle {\begin{alignedat}{2}e_{1}&=a_{1}^{*}\\e_{2}&=\left(a_{1}^{*}a_{2}^{*}a_{3}\right)^{*}\\e_{3}&=\left(\left(a_{1}^{*}a_{2}^{*}a_{3}\right)^{*}\left(a_{4}^{*}a_{5}^{*}a_{6}\right)^{*}a_{7}\right)^{*}\\e_{4}&=\left(\left(\left(a_{1}^{*}a_{2}^{*}a_{3}\right)^{*}\left(a_{4}^{*}a_{5}^{*}a_{6}\right)^{*}a_{7}\right)^{*}\left(\left(a_{8}^{*}a_{9}^{*}a_{10}\right)^{*}\left(a_{11}^{*}a_{12}^{*}a_{13}\right)^{*}a_{14}\right)^{*}a_{15}\right)^{*}\end{alignedat}}}$

Le principe de construction de ces expressions est le suivant : l’expression ${\displaystyle e_{n+1}}$ est obtenue en concaténant deux copies de ${\displaystyle e_{n}}$, où les lettres de la deuxième sont renommées par des symboles nouveau, le tout entouré d'une étoile de Kleene. Par construction, la hauteur de l'expression ${\displaystyle e_{n}}$ est n. Pour montrer que le langage dénoté par cette expression est aussi n, il reste la partie difficile à prouver, à savoir qu'il n'existe pas d'expression rationnelle de hauteur d'étoile plus petite que n décrivant le même langage que celui décrit par ${\displaystyle e_{n}}$. Une démonstration est donnée dans l'article de Eggan[3].

On peut donner une autre construction permettant de montrer que la hauteur d'étoile d'un langage n'est pas bornée. On utilise pour cela le théorème de McNaughton (vu plus haut). Pour tout n de N, on considère un langage rationnel sur un alphabet de n lettres dont l’automate minimal n’a qu’un seul état final et tel que la lecture de chacune des n lettres est une permutation des états de l’automate. Dans ce cas, le monoïde syntaxique est un groupe. Ainsi, par le théorème de McNaughton, ce langage est de hauteur d’étoile égale à n.

Le défaut des exemples de Eggan est qu'il utilise des langages ayant un nombre de lettres arbitrairement grand pour construire des langages de hauteur d'étoile de plus en plus grande. Il pose lui-même la question de savoir s'il existe des exemples avec un alphabet à deux lettres.

Une réponse positive a été donnée peu de temps après dans l'article de Dejean et Schützenberger [5]. Leurs exemples sont définis par récurrence. La famille d'expressions régulières sur l’alphabet binaire ${\displaystyle \{a,b\}}$ est la suivante[6] :

Ainsi : ${\displaystyle {\begin{alignedat}{2}e_{1}&=(ab)^{*}\\e_{2}&=\left(a^{2}(ab)^{*}b^{2}(ab)^{*}\right)^{*}\\e_{3}&=\left(a^{4}\left(a^{2}(ab)^{*}b^{2}(ab)^{*}\right)^{*}\right)^{*}b^{4}\left(a^{4}\left(a^{2}(ab)^{*}b^{2}(ab)^{*}\right)^{*}\right)^{*}\end{alignedat}}}$

À nouveau, une preuve rigoureuse est nécessaire pour démontrer que pour l'expression ${\displaystyle e_{n}}$ il n'y a pas d'expression de hauteur d'étoile plus petite. On trouve les preuves dans l'article original[5] et dans l'ouvrage de Salomaa[6].