Lemme de l'étoile

En théorie des langages, le lemme de l'étoile (ou encore lemme d'itération, lemme de pompage, lemme de la pompe, pumping lemma en anglais) énonce une propriété typique de tout langage rationnel. Informellement, il stipule que tout mot suffisamment long d'un langage rationnel peut être pompé, au sens qu'une partie centrale du mot peut être répétée un nombre quelconque de fois, et que chacun des mots produits est encore dans le langage.

Le lemme de l'étoile a été formulé pour la première fois en 1961 par Y. Bar-Hillel, Micha A. Perles, Eli Shamir. Le même article contient un lemme d'itération pour les langages algébriques.

Le lemme de l'étoile est couramment utilisé pour montrer qu'un langage donné n'est pas rationnel (en raisonnant par l'absurde). En revanche, il ne peut être employé pour démontrer qu'un langage est rationnel. En effet, il énonce une condition, nécessaire certes, mais non suffisante, de rationalité.

Énoncé formel

Lemme de l'étoile — Soit $L$ un langage rationnel. Il existe un entier $N$ tel que tout mot $w$ de $L$ de longueur $|w|\ge N$ possède une factorisation $w=xyz$ telle que

1. $0<|y|\le N$ et
2. $xy^nz \in L$ pour tout entier $n\ge0$.

Ici, $|w|\,$ dénote la longueur du mot $w$. L'entier $N$ ne dépend que de $L$ et non pas du mot $w$ choisi. Il est parfois appelé «constante d'itération». Le facteur central $y$ de la factorisation $w=xyz$ est appelé un « facteur itérant ». Le nom « lemme de l'étoile » provient de la formulation équivalente suivante de la conclusion du lemme:

$xy^*z \subset L$.

Parmi les itérés $xy^nz$ qui sont dans le langage figure aussi le mot $xz$ obtenu pour $n=0$.

Il existe de nombreuses variantes de ce lemme; la plus fréquente stipule, au lieu de la condition $|y|\le N$, la condition $|xy|\le N$, et donc que le facteur itérant $y$ se situe près du début du mot.

Un exemple d'application du lemme de l'étoile

Le lemme de l'étoile est souvent utilisé pour démontrer qu'un langage donné n'est pas rationnel. La preuve se fait en général par l'absurde, en supposant que le langage est rationnel et en exhibant un mot du langage qui ne vérifie pas la conclusion du lemme.

Prenons par exemple le langage $L = \{a^n b^n \mid n\ge0\}$ sur l'alphabet $A= \{a,b\}$. Supposons par l'absurde que $L$ est rationnel. Soit $N$ la constante d'itération de $L$. On choisit le mot $w = a^N b^N$. Par le lemme, il existe un mot $w=xyz$ vérifiant les conditions du lemme de l'étoile. En particulier, et en utilisant la variante énoncée, on a $|xy| \le N$, et donc $x$ et $y$ sont composés uniquement de lettres $a$. Posons $k=|y|\,$. On a $k>0$. Alors $xy^nz = a^{N+(n-1)k}b^N$ pour tout entier $n\ge0$. Comme ces mots devraient être dans $L$ on devrait avoir ${N+(n-1)k}=N$ pour tout entier $n\ge0$ et donc $k=|y|=0\,$, ce qui est en contradiction avec l'hypothèse. Donc $L$ n'est pas rationnel.

On montre de même que

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

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

Preuve du lemme de l'étoile

L'argument principal de la preuve est le principe des tiroirs. Il s’emploie, dans le cas présent, sous la forme du constat qu'un chemin assez long dans un graphe fini passe deux fois par le même sommet.

Soit $L$ un langage rationnel, sur un alphabet $A$. Par le théorème de Kleene, il existe un automate fini $\mathcal{A}$ qui reconnaît $L$. Soit $N$ le nombre d'états de cet automate.

Soit $w$ un mot de $L$ de longueur $|w|\ge N\,$. Comme $w$ est dans $L$, il est reconnu par $\mathcal{A}$, et il existe un chemin réussi $q_0 \xrightarrow{w}t$ de l'état initial noté ici $q_0$ vers un état terminal $t$ d'étiquette $w$. Soient $a_1,a_2,\ldots,a_N$ les $N$ premières lettres de $w$, posons $w=a_1a_2\cdots a_Nw'$, et soient $q_1,q_2,\ldots,q_N$ les états successifs atteints après la lecture de ces lettres. On a alors le chemin suivant

$q_0\xrightarrow{a_1}q_1\xrightarrow{a_2}q_2\cdots q_{N-1}\xrightarrow{a_N}q_N\xrightarrow{w'}t.$

Le principe des tiroirs dit que, parmi les $N+1$ états $q_0,q_1,\ldots,q_N$, deux sont égaux. Il existe donc deux entiers $k,\ell$ avec $0\le k<\ell\le N$ tels que $q_k=q_\ell$. Posons $q=q_k=q_\ell$ et

$x=a_1a_2\cdots a_k,\ y=a_{k+1}\cdots a_\ell,\ z=a_\ell\cdots a_Nw'.$

Le chemin d'étiquette $w$ se factorise de la façon suivante:

$q_0\xrightarrow{x}q\xrightarrow{y}q\xrightarrow{z}t.$

Il en résulte que $q\xrightarrow{y^n}q$ pour tout entier $n\ge0$, et donc que $xy^nz$ est dans $L$ pour tout entier $n\ge0$. Enfin, on a $|y|=\ell-k$, donc $0<|y|\le N$. Ceci prouve le lemme.

La preuve montre en fait la variante du lemme énoncée ci-dessus, à savoir que de plus on a $|xy|\le N$, puisque $|xy|=\ell$.

Le lemme est une condition nécessaire mais non suffisante de rationalité

Le lemme ne donne qu'une condition nécessaire pour qu'un langage soit rationnel. Voici un exemple d'un langage non rationnel qui vérifie le lemme de l'étoile dans la version donnée ci-dessus.

Notons $u^R$ l'image miroir d'un mot $u$, et soit $L = \{ uu^Rv\mid\ u,v \in \{a,b\}^+\}$ l'ensemble des mots qui ont un préfixe qui est un palindrome non vide de longueur paire.

Posons $N=4$, et soit $w = uu^Rv$ un mot de longueur au moins 4 du langage. Si $u$ est une lettre, la factorisation $w=xyz$ avec $x=uu^R$, $y$ la première lettre de $v$ et $z$ le reste du mot convient. Si $u$ est de longueur au moins 2, on choisit pour $x$ le mot vide, pour $y$ la première lettre de $u$, et pour $z$ le $u$ reste du mot. Pour $N\ge2$, le mot $xy^Nz$ commence par le palindrome non vide $yy$; pour $N=0$, le mot $xy^Nz=z$ commence par le palindrome formé de $u$ privé de sa première lettre, suivi de l'image miroir de ce suffixe (lui-même suivi de la première lettre de $u$).

Extensions

Il existe de nombreuses variantes du lemme de l'étoile, plus ou moins sophistiquées, pour prendre en compte des langages plus compliqués.

Choix du facteur itérant

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é:

Lemme de l'étoile (variante) — Soit $L$ un langage rationnel. Il existe un entier $N$ tel que pour tout mot $w$ de $L$, et pour toute factorisation $w=uw'v$, avec $w'$ de longueur $|w'|\ge N$, il existe une factorisation $w'=xyz$ telle que

1. $0<|y|\le N$ et
2. $uxy^*zv \subset L$.

Lemme de l'étoile par bloc

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

Lemme de l'étoile par blocs — Soit $L$ un langage rationnel. Il existe un entier $N$ tel que pour tout mot $w$ de $L$, et pour toute factorisation $w=uw_1w_2\cdots w_Nv$, où tous les $w_i$ sont non vides, il existe deux entiers $k,\ell$ avec

1. $0\le k<\ell\le N$ et
2. $uw_1w_2\cdots w_k(w_{k+1}\cdots w_\ell)^*w_{\ell+1}\cdots w_Nv\subset L$.

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

Lemme de l'étoile à la Ogden

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

Lemme de l'étoile à la Ogden — Soit $L$ un langage rationnel. Il existe un entier $N$ tel que pour tout mot $w$ de $L$ de longueur $|w|\ge N$, et pour tout choix de $N$ positions distinguées dans $w$, il existe une factorisation $w=xyz$ telle que

1. $y$ contient au moins une et au plus $N$ positions distinguées
2. $xy^*z \subset L$.

Si l'on distingue toutes les positions dans $w$, on retrouve le lemme de l'étoile initial. Si l'on considère la factorisation de $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 condition nécessaire et suffisante

Un théorème prouvé par Ehrenfeucht (en), Parikh (en) et Rozenberg (en) donne une condition qui est nécessaire et suffisante pour qu'un langage soit rationnel. On dit qu'un langage $L$ sur l'alphabet $A$ vérifie la condition $(E_N)$ pour un entier $N$ si pour tout mot $w$, et pour toute factorisation $w=w=uw_1w_2\cdots w_Nv$, où les mots $w_i$ sont non vides, il existe deux indices $k,\ell$ avec $0\le k<\ell\le N$ tels que

pour tout $n\qquad$,on a $\qquad w\in L \iff uw_1w_2\cdots w_k(w_{k+1}\cdots w_\ell)^nw_{\ell+1}\cdots w_Nv\in L$.

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

$\qquad w\in L \implies uw_1w_2\cdots w_k(w_{k+1}\cdots w_\ell)^*w_{\ell+1}\cdots w_Nv\subset L$ et

$\qquad w\in A^*\setminus L \implies uw_1w_2\cdots w_k(w_{k+1}\cdots w_\ell)^*w_{\ell+1}\cdots w_Nv\subset A^*\setminus L$

On dit que $L$ vérifie la condition $(E'_N)$ si pour tout mot $w$, et pour toute factorisation $w=w=uw_1w_2\cdots w_Nv$, où les mots $w_i$ sont non vides, il existe deux indices $k,\ell$ avec $0\le k<\ell\le N$ tels que

$w\in L \iff uw_1w_2\cdots w_kw_{\ell+1}\cdots w_Nv\in L$.

Théorème d'Ehrenfeucht, Parikh et Rozenberg — Soit $L$ un langage. Les conditions suivantes sont équivalentes:

1. $L$ est rationnel;
2. Il existe un entier $N$ tel que $L$ vérifie la condition $(E_N)$
3. Il existe un entier $N$ tel que $L$ vérifie la condition $(E'_N)$.

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

Références

• Yehoshua Bar-Hillel, Micha A. Perles et Eli Shamir, « On formal properties of simple phrase structure grammars », dans Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung, vol. 14, 1961, p. 143-172 

• William F. Ogden, « A Helpful Result for Proving Inherent Ambiguity », dans Mathematical Systems Theory, vol. 2, n^o 3, 1968, p. 191-194 [lien DOI] 

• Andrzej Ehrenfeucht, Rohit Jivanlal Parikh et Grzegorz Rozenberg, « Pumping lemmas for regular sets », dans SIAM J. Comput., vol. 10, 1981, p. 536–541 

• Olivier Carton, Langages formels, calculabilité et complexité, Vuibert, 2008 (ISBN 978-2-7117-2077-4) 

Voir aussi

• Expression rationnelle
• Théorème de Kleene
• Lemme d'itération
• Lemme d'itération pour les langages algébriques
• Lemme d'Ogden