Lemme de l'étoile

Montrons par exemple que le langage ${\displaystyle L=\{a^{n}b^{n}\mid n\geq 0\}}$ sur l'alphabet ${\displaystyle A=\{a,b\}}$ n'est pas rationnel. Il s'agit du langage qui des mots qui commencent par un certain nombre de ${\displaystyle a}$, suivi par le même nombre de ${\displaystyle b}$. Il contient le mot vide, ${\displaystyle ab}$, ${\displaystyle aabb}$, ${\displaystyle aaabbb}$, etc. Supposons par l'absurde que ${\displaystyle L}$ est rationnel. Dans ce cas, on peut appliquer le lemme de l'étoile. Soit ${\displaystyle N}$ une constante d'itération de ${\displaystyle L}$. Considérons le mot ${\displaystyle w=a^{N}b^{N}}$. Par le lemme, il existe un mot ${\displaystyle w=xyz}$ vérifiant les conditions du lemme de l'étoile. En particulier, et en utilisant la variante énoncée, on a ${\displaystyle |xy|\leq N}$, et donc ${\displaystyle x}$ et ${\displaystyle y}$ sont composés uniquement de lettres ${\displaystyle a}$. Posons ${\displaystyle k=|y|\,}$. On a ${\displaystyle k>0}$ et ${\displaystyle y=a^{k}}$. Alors ${\displaystyle xy^{n}z=a^{N+(n-1)k}b^{N}}$ pour tout entier ${\displaystyle n\geq 0}$. Comme ces mots devraient être dans ${\displaystyle L}$ on devrait avoir ${\displaystyle {N+(n-1)k}=N}$ pour tout entier ${\displaystyle n\geq 0}$ et donc ${\displaystyle k=|y|=0\,}$, ce qui est en contradiction avec l'hypothèse. Donc ${\displaystyle L}$ n'est pas rationnel.

On montre de même que

• le langage des palindromes sur ${\displaystyle A=\{a,b\}}$ n'est pas rationnel,
• le langage ${\displaystyle \{w\in X^{*}:|w|_{a}=|w|_{b}\}}$ sur ${\displaystyle A=\{a,b\}}$ (où ${\displaystyle |w|_{a}\,}$ désigne le nombre d'occurrences de la lettre ${\displaystyle a}$ dans le mot ${\displaystyle w}$) est composé des mots qui ont autant de ${\displaystyle a}$ que de ${\displaystyle b}$. Il n'est pas rationnel.

Un peu plus compliqué est la preuve que le langage ${\displaystyle \{a^{n}b^{m}\mid 0\leq n\leq m\}}$ n'est pas rationnel. De même, le langage ${\displaystyle \{a^{n}b^{m}\mid n\neq m\}}$ n'est pas rationnel. Au lieu de faire une preuve directe, il vaut mieux passer par le langage complément.

La première variante énonce que la place du facteur itérant peut être choisie dans n'importe quelle plage du mot de longueur assez grande. Voici l'énoncé :

Sur l'alphabet ${\displaystyle \{a,b\}}$, en posant, pour tout mot ${\displaystyle u}$ sur cet alphabet: ${\displaystyle |u|_{a}}$ et ${\displaystyle |u|_{b}}$, respectivement le nombre de ${\displaystyle a}$ et le nombre de ${\displaystyle b}$ dans ${\displaystyle u}$,  on a que l'ensemble des mots ${\displaystyle u}$ tels que ${\displaystyle |u|_{a}=|u|_{b}}$ vérifie la conclusion du lemme de l'étoile (en prenant ${\displaystyle N=2}$, il existe, dans tous mots de cet ensemble, un ${\displaystyle a}$ et un ${\displaystyle b}$ se suivant; il est possible d'itérer cette partie du mot en restant dans ce langage: par exemple, si le mot est de la forme ${\displaystyle vabv'}$ (le cas ${\displaystyle vbav'}$ étant similaire), on a que, pour tout entier naturel n, ${\displaystyle v(ab)^{n}v'}$ est également dans le langage). Cependant, il ne respecte pas le lemme de l'étoile par blocs: par l'absurde, on suppose disposer d'un tel ${\displaystyle N}$. On pose alors: ${\displaystyle w=a^{N}b^{N}}$ et ${\displaystyle u=a^{N}}$, ${\displaystyle w'=b^{N}}$ et ${\displaystyle v}$, le mot vide. On dispose alors d'une factorisation de la forme: ${\displaystyle w'=xyz}$ respectant la conclusion du choix du facteur itérant. Or: ${\displaystyle |uxy^{2}zv|_{b}>|uxyzv|_{b}}$ et ${\displaystyle |uxy^{2}zv|_{a}=|uxyzv|_{a}}$, ce qui est absurde.

Le schéma de la preuve est semblable à celui du premier lemme de l'étoile énoncé. Soit ${\displaystyle L}$ un langage rationnel, sur un alphabet ${\displaystyle A}$, soit ${\displaystyle {\mathcal {A}}}$, un automate fini reconnaissant ${\displaystyle L}$ et soit ${\displaystyle N}$ son nombre d'états. Soit ${\displaystyle w}$ un mot de ${\displaystyle L}$, et soit ${\displaystyle uw'v}$, une factorisation de ce mot telle que ${\displaystyle |w'|\geq N}$. On pose ${\displaystyle w'=a_{1}\cdots a_{N}s}$ où les ${\displaystyle a_{i}}$ sont des lettres et où ${\displaystyle s}$ le suffixe de ${\displaystyle w'}$ la longueur ${\displaystyle |w'|-N}$. Il existe une suite ${\displaystyle i,q_{0},q_{1},\ldots ,q_{N},q',t}$ d'états, où ${\displaystyle i}$ est initial et ${\displaystyle t}$ est terminal, tels que

${\displaystyle i{\stackrel {u}{\longrightarrow }}q_{0}}$, ${\displaystyle q_{0}{\stackrel {a_{1}}{\longrightarrow }}q_{1}{\stackrel {a_{2}}{\longrightarrow }}q_{2}\cdots q_{N-1}{\stackrel {a_{N}}{\longrightarrow }}q_{N}}$ et ${\displaystyle q_{N}{\stackrel {s}{\longrightarrow }}q'{\stackrel {v}{\longrightarrow }}t}$.

Par le principe des tiroirs, il existe deux entiers ${\displaystyle 0\leq k<\ell \leq N}$ tels que ${\displaystyle q_{k}=q_{\ell }}$. Posons

${\displaystyle q=q_{k}=q_{\ell }}$, ${\displaystyle x=a_{1}\cdots a_{k},y=a_{k+1}\cdots a_{\ell }}$, ${\displaystyle z=a_{\ell +1}\cdots a_{N}s}$.

Alors

${\displaystyle q_{0}{\stackrel {x}{\longrightarrow }}q{\stackrel {y}{\longrightarrow }}q{\stackrel {z}{\longrightarrow }}q'}$ et de plus ${\displaystyle q{\stackrel {y^{n}}{\longrightarrow }}q}$

pour tout entier naturel ${\displaystyle n}$. L'automate reconnaît donc tous les mots de la forme ${\displaystyle uxy^{n}zv}$, et de plus ${\displaystyle 0<|y|=\ell -k-1\leq N}$.

Dans cette variante, on découpe le mot en blocs, et c'est un groupe de blocs que l'on peut itérer:

Dans cet énoncé et les suivants, on convient que ${\displaystyle w_{1}w_{2}\cdots w_{k}}$ est égal au mot vide si ${\displaystyle k=0}$, et de même ${\displaystyle w_{\ell +1}\cdots w_{N}}$ est égal au mot vide si ${\displaystyle \ell =N}$.

Soit ${\displaystyle L}$ un langage rationnel. Par théorème de Kleene, il existe un automate fini ${\displaystyle {\mathcal {A}}}$ reconnaissant ${\displaystyle L}$. Soit ${\displaystyle N}$ le nombre d'états de ${\displaystyle {\mathcal {A}}}$ et soit ${\displaystyle w=uw_{1}\cdots w_{N}v}$ un mot de ${\displaystyle L}$ Il existe une suite d'états ${\displaystyle i,q_{0},q_{1},\ldots ,q_{N},t}$ tels que

${\displaystyle i{\stackrel {u}{\longrightarrow }}q_{0}{\stackrel {w_{1}}{\longrightarrow }}q_{1}\ \cdots \ q_{N-1}{\stackrel {w_{N}}{\longrightarrow }}q_{N}{\stackrel {v}{\longrightarrow }}t}$,

où ${\displaystyle i}$ est initial et ${\displaystyle t}$ est terminal. Par le principe des tiroirs, il existe deux indice ${\displaystyle 0\leq k<\ell \leq N}$ tels que ${\displaystyle q_{k}=q_{\ell }}$. On a donc, en notant ${\displaystyle q}$ cet état et ${\displaystyle z=w_{k+1}\cdots w_{\ell }}$, que

${\displaystyle q{\stackrel {z}{\longrightarrow }}q}$

dans l'automate. On en déduit le résultat souhaité : pour tout entier naturel ${\displaystyle n}$, le mot${\displaystyle w=uw_{1}\cdots w_{k}z^{n}w_{\ell +1}\cdots w_{N}v}$ est un mot accepté par l'automate et est donc un mot de ${\displaystyle L}$.

La réciproque de ce lemme est fausse (il ne s'agit donc pas d'une condition nécessaire et suffisante). Un exemple est donné ci-dessous.

Soient ${\displaystyle A=\{a,b,c\}}$ et ${\displaystyle B=\{a,b,c,\#\}}$ ; soit ${\displaystyle K=\{uu\mid \ u\in \ A^{+}\}}$ et ${\displaystyle K'=\{u\#v\mid \ u,v\in \ A^{*}{\text{ et }}u\neq v\}}$. Le langage ${\displaystyle L}$ défini par:

${\displaystyle L=K'\cup A^{*}KA^{*}\#A^{*}\cup A^{*}\#A^{*}KA^{*}}$

vérifie la conclusion du lemme de l'étoile par blocs. Cependant, il n'est pas rationnel[2].

Le lemme d'Ogden[3], initialement conçu pour les langages algébriques, s'applique aussi bien aux langages rationnels. Étant donné un mot ${\displaystyle w=a_{1}a_{2}\cdots a_{n}}$, où les ${\displaystyle a_{i}}$ sont des lettres, on appelle position dans ${\displaystyle w}$ tout entier de l'ensemble ${\displaystyle \{1,2,\ldots ,n\}}$. Un choix de ${\displaystyle N}$ positions distinguées dans ${\displaystyle w}$ (ceci est la terminologie habituelle, un peu alambiquée) est simplement un sous-ensemble ${\displaystyle I\subset \{1,2,\ldots ,n\}}$ de positions contenant ${\displaystyle N}$ éléments. Avec ces définitions, le lemme s'énonce comme suit:

Si l'on distingue toutes les positions dans ${\displaystyle w}$, on retrouve le lemme de l'étoile initial. Si l'on considère la factorisation de ${\displaystyle w}$ obtenue en segmentant le mot après chaque position distinguée, on obtient essentiellement le lemme de l'étoile par blocs. Les preuves de ces énoncés sont très similaires.

Une première caractérisation, qui se fonde sur un renforcement du lemme de l'étoile « faible » est celle de J. Jaffe[4].

On dit qu'un langage ${\displaystyle L}$ satisfait la condition ${\displaystyle (J_{N})}$ pour un certain entier naturel ${\displaystyle N}$ si pour tout mot ${\displaystyle w}$ de longueur ${\displaystyle N}$, il existe une factorisation ${\displaystyle w=uvz}$ avec ${\displaystyle v}$ non vide telle que: ${\displaystyle \forall t\in A^{*},\forall n\in \mathbb {N} ,wt\in L\iff uv^{n}zt\in L}$

On dit qu'un langage ${\displaystyle L}$ satisfait la condition ${\displaystyle (J'_{N})}$ pour un certain entier naturel ${\displaystyle N}$ si pour tout mot ${\displaystyle w}$ de longueur ${\displaystyle N}$, il existe une factorisation ${\displaystyle w=uvz}$ avec ${\displaystyle v}$ non vide telle que: ${\displaystyle \forall t\in A^{*},wt\in L\iff uzt\in L}$

On a alors le théorème de Jaffe:

Elle est cependant « non-locale » puisque pour chaque mot, il faut trouver une factorisation qui marche uniformément par rapport à tous les quotients à droite de ce mot.

Un théorème prouvé par Andrzej Ehrenfeucht, Rohit Jivanlal Parikh et Grzegorz Rozenberg[5] donne une condition, fondée sur un renforcement du lemme de l'étoile par blocs, qui est nécessaire et suffisante pour qu'un langage soit rationnel et qui est « locale » au sens précédent.

On dit qu'un langage ${\displaystyle L}$ sur l'alphabet ${\displaystyle A}$ vérifie la condition ${\displaystyle (E_{N})}$ pour un entier ${\displaystyle N}$ si pour tout mot ${\displaystyle w}$, et pour toute factorisation ${\displaystyle w=w=uw_{1}w_{2}\cdots w_{N}v}$, où les mots ${\displaystyle w_{i}}$ sont non vides, il existe deux indices ${\displaystyle k,\ell }$ avec ${\displaystyle 0\leq k<\ell \leq N}$ tels que

${\displaystyle w\in L\iff uw_{1}w_{2}\cdots w_{k}(w_{k+1}\cdots w_{\ell })^{n}w_{\ell +1}\cdots w_{N}v\in L}$ pour tout ${\displaystyle n\in \mathbb {N} }$.

L'équivalence équivaut à la conjonction des deux implications :

${\displaystyle w\in L\implies uw_{1}w_{2}\cdots w_{k}(w_{k+1}\cdots w_{\ell })^{*}w_{\ell +1}\cdots w_{N}v\subset L}$ et

${\displaystyle w\in A^{*}\setminus L\implies uw_{1}w_{2}\cdots w_{k}(w_{k+1}\cdots w_{\ell })^{*}w_{\ell +1}\cdots w_{N}v\subset A^{*}\setminus L}$.

On dit que ${\displaystyle L}$ vérifie la condition ${\displaystyle (E'_{N})}$ si pour tout mot ${\displaystyle w}$, et pour toute factorisation ${\displaystyle w=w=uw_{1}w_{2}\cdots w_{N}v}$, où les mots ${\displaystyle w_{i}}$ sont non vides, il existe deux indices ${\displaystyle k,\ell }$ avec ${\displaystyle 0\leq k<\ell \leq N}$ tels que

${\displaystyle w\in L\iff uw_{1}w_{2}\cdots w_{k}w_{\ell +1}\cdots w_{N}v\in L}$.

Il convient de noter une différence importante avec le théorème de Jaffe énoncée précédemment. Les conditions ${\displaystyle (J_{N})}$ et ${\displaystyle (J'_{N})}$ portent sur une factorisation d'un mot et de tous ses quotients à droite tandis que les conditions ${\displaystyle (E_{N})}$ et ${\displaystyle (E'_{N})}$ portent sur toutes les factorisations possibles d'un seul mot, ce qui assure leur caractère local.

L'implication difficile est ${\displaystyle (3)\implies (1)}$. Elle utilise, à la place du principe des tiroirs, le théorème de Ramsey.

Preuve de l'implication ${\displaystyle (1)\implies (2)}$

Si ${\displaystyle L}$ est rationnel alors son complémentaire ${\displaystyle A^{*}\setminus L}$ est aussi rationnel. On applique alors le lemme de l'étoile par blocs à ${\displaystyle L}$ et à ${\displaystyle A^{*}\setminus L}$, ce qui fournit deux entiers ${\displaystyle N_{1}}$ et ${\displaystyle N_{2}}$ respectivement. On définit ${\displaystyle N=max\{N_{1},N_{2}\}}$. Soient alors un mot ${\displaystyle w}$ et une factorisation ${\displaystyle w=w=uw_{1}w_{2}\cdots w_{N}v}$, où les mots ${\displaystyle w_{i}}$ sont non vides. Si ${\displaystyle w\in L}$, alors il existe deux indices ${\displaystyle k,\ell }$ avec ${\displaystyle 0\leq k<\ell \leq N_{1}\leq N}$ tels que ${\displaystyle uw_{1}w_{2}\cdots w_{k}(w_{k+1}\cdots w_{\ell })^{*}w_{\ell +1}\cdots w_{N}v\subset L}$. De même, si ${\displaystyle w\in A^{*}\setminus L}$, alors il existe deux indices ${\displaystyle k,\ell }$ avec ${\displaystyle 0\leq k<\ell \leq N_{2}\leq N}$ tels que ${\displaystyle uw_{1}w_{2}\cdots w_{k}(w_{k+1}\cdots w_{\ell })^{*}w_{\ell +1}\cdots w_{N}v\subset A^{*}\setminus L}$. Finalement on obtient bien que ${\displaystyle L}$ vérifie la condition ${\displaystyle (E_{N})}$.

Preuve de l'implication ${\displaystyle (2)\implies (3)}$

Si ${\displaystyle L}$ vérifie ${\displaystyle (E_{N})}$ pour un certain entier ${\displaystyle N}$ alors pour tout mot et toute factorisation, en prenant ${\displaystyle n=0}$ dans l'équivalence sus-citée attachée à la condition ${\displaystyle (E_{N})}$, on obtient que ${\displaystyle L}$ vérifie ${\displaystyle (E'_{N})}$.

Preuve de l'implication ${\displaystyle (3)\implies (1)}$

On s'inspire ici de l'exposition donnée dans les livres de Carton et de Sakarovitch[6]. On procède en trois étapes:

• a) On montre que si ${\displaystyle L}$ vérifie la condition ${\displaystyle (E'_{N})}$ pour un certain entier naturel ${\displaystyle N}$ alors ses quotients à gauche aussi.
• b) On montre, grâce au théorème de Ramsey, que pour tout entier naturel ${\displaystyle N}$, le nombre de langages vérifiant la condition ${\displaystyle (E'_{N})}$ est fini.
• c) On utilise le théorème de Myhill-Nerode pour conclure : le langage ${\displaystyle L}$, ayant un nombre fini de quotients à gauche, est reconnaissable par un automate fini, donc rationnel d'après le théorème de Kleene.

Preuve du point a): Soient ${\displaystyle N\in \mathbb {N} }$ et ${\displaystyle L}$ vérifiant la condition ${\displaystyle (E'_{N})}$. Soit ${\displaystyle f}$ un mot. Soient ${\displaystyle w}$ un mot et soit ${\displaystyle w=w=uw_{1}w_{2}\cdots w_{N}v}$ une factorisation, où les mots ${\displaystyle w_{i}}$ sont non vides. Grâce à la condition ${\displaystyle (E'_{N})}$, on sait qu'il existe deux indices ${\displaystyle k,\ell }$ avec ${\displaystyle 0\leq k<\ell \leq N}$ tels que:

${\displaystyle fw\in L\iff fuw_{1}w_{2}\cdots w_{k}w_{\ell +1}\cdots w_{N}v\in L}$.

On a alors:

${\displaystyle {\begin{aligned}w\in f^{-1}L&\iff fw\in L\iff fuw_{1}w_{2}\cdots w_{k}w_{\ell +1}\cdots w_{N}v\in L\\&\iff uw_{1}w_{2}\cdots w_{k}w_{\ell +1}\cdots w_{N}v\in f^{-1}L\end{aligned}}}$

ce qui montre que ${\displaystyle f^{-1}L}$ vérifie la condition ${\displaystyle (E'_{N})}$.

Preuve du point b): On utilise le théorème de Ramsey sous la forme suivante, équivalente à celle énoncée pour les graphes dans l'article théorème de Ramsey. Dans cet énoncé, ${\displaystyle P_{k}(X)}$ dénote l'ensemble des parties à ${\displaystyle k}$ éléments d'un ensemble ${\displaystyle X}$.

Théorème de Ramsey pour les ensembles finis — Pour tout triplet ${\displaystyle (k,m,r)\in \mathbb {N} ^{3}}$, il existe un entier ${\displaystyle R=R(k,m,r)}$ tel que pour tout ensemble ${\displaystyle E}$ d'au moins ${\displaystyle R}$ éléments et pour toute partition de ${\displaystyle P_{k}(E)}$ en au plus ${\displaystyle m}$ classes, il existe un sous-ensemble ${\displaystyle F}$ de ${\displaystyle E}$ d'au moins ${\displaystyle r}$ éléments tel que ${\displaystyle P_{k}(F)}$ est entièrement contenu dans l'une des classes de la partition.

Soient donc ${\displaystyle N\in \mathbb {N} }$ et ${\displaystyle R=R(2,2,N+1)}$. Montrons que si deux langages ${\displaystyle L}$ et ${\displaystyle K}$ vérifiant la condition ${\displaystyle (E'_{N})}$ coïncident sur les mots de longueur ${\displaystyle \leq R}$ alors ils sont égaux. Ceci fournira une injection de l'ensemble des langages vérifiant ${\displaystyle (E'_{N})}$ vers l'ensemble des parties de l'ensemble des mots de longueur ${\displaystyle \leq R}$, qui est un ensemble fini, ce qui permettra de conclure.

Pour ce faire, on procède par récurrence forte sur la longueur d'un mot. Si ${\displaystyle w}$ est un mot de longueur ${\displaystyle \leq R}$ alors ${\displaystyle w\in L\iff w\in K}$ par hypothèse. On suppose maintenant que ${\displaystyle w}$ est de longueur ${\displaystyle M>R}$ et que ${\displaystyle L}$ et ${\displaystyle K}$ coïncident sur les mots de longueur ${\displaystyle <M}$. On factorise ${\displaystyle w}$ en ${\displaystyle w=w_{0}w_{2}\cdots w_{R}v}$ où les ${\displaystyle w_{i}}$ sont des lettres et ${\displaystyle v}$ un mot. On considère l'ensemble ${\displaystyle E=\{1,\ldots ,R\}}$ et la partition ${\displaystyle \{X,{\bar {X}}\}}$ de ${\displaystyle P_{2}(E)}$ où

${\displaystyle X=\{\{i,j\}\in P_{2}(E)\mid i<j\ \ {\text{et}}\ \ w_{0}w_{2}\cdots w_{i}w_{j+1}\cdots w_{N}v\in L\}}$

et son complémentaire noté ${\displaystyle {\bar {X}}}$. Par hypothèse de récurrence, on a aussi

${\displaystyle X=\{\{i,j\}\in P_{2}(E)\mid i<j\ \ {\text{et}}\ \ w_{0}w_{2}\cdots w_{i}w_{j+1}\cdots w_{N}v\in K\}}$.

Par le théorème de Ramsey, on obtient l'existence d'un sous-ensemble ${\displaystyle F=\{i_{1}<\cdots <i_{N}\}}$ de ${\displaystyle E}$ tel que ${\displaystyle P_{2}(F)\subset X}$ ou ${\displaystyle P_{2}(F)\subset {\bar {X}}}$. On obtient alors une nouvelle factorisation ${\displaystyle w=uv_{1}\cdots v_{N}z}$ avec

${\displaystyle u=w_{0}\cdots w_{i_{0}-1}}$ , ${\displaystyle v_{j}=w_{i_{j-1}}w_{i_{j-1}+1}\cdots w_{i_{j}-1}}$ pour ${\displaystyle j=1,\ldots ,N}$ et ${\displaystyle z=w_{i_{N}}\cdots v}$.

Puisque ${\displaystyle L}$ et ${\displaystyle K}$ vérifient la condition ${\displaystyle (E'_{N})}$, cette factorisation donne deux paires ${\displaystyle (m,n)\in [[0,N]]^{2}}$ et ${\displaystyle (m',n')\in [[0,N]]^{2}}$ respectivement qui délimitent des blocs qu'on peut éliminer dans ${\displaystyle w}$. Plus précisément :

${\displaystyle {\begin{aligned}w\in L&\iff w_{0}\cdots w_{i_{m}}w_{i_{n}+1}\cdots w_{N}v\in L\\&\iff w_{0}\cdots w_{i_{m'}}w_{i_{n}'+1}\cdots w_{N}v\in L\\&\iff w_{0}\cdots w_{i_{m'}}w_{i_{n}'+1}\cdots w_{N}v\in K\iff w\in K\end{aligned}}}$

par définition de ${\displaystyle (m,n)}$, ${\displaystyle F}$ et ${\displaystyle (m',n')}$ successivement. Ceci fournit l'hérédité de la propriété et permet de conclure la récurrence. On obtient finalement que si les langages ${\displaystyle L}$ et ${\displaystyle K}$ coïncident sur les mots de longueur ${\displaystyle <R}$, ils sont égaux, ce qui achève la preuve du point b).