Lemme de l'étoile

En théorie des langages, le lemme de l'étoile (ou encore lemme d'itération, lemme de pompage, pumping lemma en anglais) décrit une propriété essentielle de tout langage rationnel. Informellement, il établit que tout mot suffisamment long d'un langage rationnel peut être pompé, c'est-à-dire qu'une partie centrale du mot peut être répétée un nombre arbitraire de fois pour produire un nouveau mot qui se trouve encore dans le langage initial.

Le lemme de l'étoile a été imaginé pour la première fois par Y. Bar-Hillel, Micha A. Perles, Eli Shamir en 1961. Il est très pratique pour montrer qu'un langage donné n'est pas rationnel (en raisonnant par l'absurde).

Soit L un langage rationnel sur l'alphabet X.

Alors il existe un entier p tel que :

1. w = xyz,
2. $y\ne \epsilon ,$
3. $|xy|⩽p$
4. $\forall n\in \mathbb{N},x{y}^{n}z\in L.$

$|w|$ désigne la longueur du mot w. L'entier p ne dépend que de L et est parfois appelé "longueur de pompage". (1) signifie que w est divisé en trois facteurs ; (2) signifie que y doit être de longueur au moins 1 ; (3) signifie que la "pompe" y doit se trouver dans les p premières lettres de w. Il n'y a pas de restrictions sur x et z.

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 de longueur suffisante tel que la propriété (4) du lemme n'est pas vérifiée.

Prenons par exemple le langage $L=\{a^n{b}^n/n\in \mathbb{N}\}$ sur l'alphabet Σ = {a,b}. Supposons par l'absurde que L est rationnel. On fixe l'entier p apparaissant dans l'énoncé du lemme. On choisit le mot w = a**b. Il existe donc une décomposition(d´apres la condition (1) du lemme) w = xyz vérifiant les conditions (2), (3), (4)du lemme de l'étoile. | x**y | < p donc il existe deux entiers i et j tels que i + j < p et x = a,y = a. De plus j > 0 car y n'est pas le mot vide. Il en résulte que z = a**b. On devrait ainsi avoir $xz=x{y}^{0}z=a^{p-j}{b}^p\in L$, ce qui est absurde car p − j < p. Donc L n'est pas rationnel.

On montre de même que

• le langage des palindromes sur Σ = {a,b} n'est pas rationnel,
• le langage $L^{\prime }=\{w\in X^{\ast }/|w{|}_a=|w{|}_b\}$ sur Σ = {a,b} n'est pas rationnel (où | w | _a désigne le nombre d'occurrences de la lettre a dans le mot w).

Voici un automate fini reconnaissant le langage décrit par l'expression rationnelle a(bc)*d.

L'automate fini reconnaît le mot abcbcd. Comme il contient plus de lettres que le nombre d'états de l'automate, tout chemin étiqueté par abcbcd dans l'automate comportera au moins un état répété. Ici, l'état q₁ est répété. On comprend ainsi que ad appartient au langage reconnu par l'automate, en empruntant le chemin $q_0\stackrel{a}{⟶}{q}_1\stackrel{d}{⟶}{q}_3$. De même, en répétant la boucle bc, tout mot de la forme a(b**c)d avec $n\in \mathbb{N}$ sera reconnu par l'automate.

On pressent donc que la démonstration reposera sur le nombre d'état d'un automate reconnaissant le langage rationnel en question, et sur la répétition d'états lors de la lecture d'un mot.

Rappel : si L est un langage rationnel, alors il existe un automate fini reconnaissant le langage L.

On considère un langage rationnel L.

Premier cas : si L est fini, alors on choisit $p>{\max }_{w\in L}|w|$. Alors il n'existe pas de mot w appartenant à L tel que $|w|⩾p$, donc l'assertion à vérifier est triviale.

Deuxième cas : si L est infini.
Il existe un automate fini A qui reconnaît L. Le nombre d'états de A étant fini, on note p ce nombre augmenté de 1.
Soit maintenant w un mot de L tel que $|w|⩾p$. w est reconnu par A, donc il existe un chemin $q_0\stackrel{w}{⟶}{q}_n$ réussi dans A, étiqueté par w. Autrement dit, q₀ est un état initial de A, et en partant de cet état on peut lire l'une après l'autre toutes les lettres de w en terminant la lecture par un état q_n acceptant de A. Ceci impose $n=|w|⩾p$, ce qui assure par la définition de p qu'un certain état $q=q_i,i\in \{\mathrm{0..}n\}$ intervient au moins deux fois dans le chemin parcouru pour lire w.
On peut choisir i minimal. q est ainsi décrit comme la première occurrence du premier état q répété au cours du chemin $q_0⟶q_n$. On note alors y le mot qui est lu entre q_i et q_j, la deuxième occurrence de q dans le chemin en question (avec donc $n⩾j>i$). On note x le mot lu entre q₀ et q_i, et z le mot lu entre q_j et q_n. Ainsi, w = xyz.
On remarque que x et z peuvent être vides, mais y ne l'est pas. Vu la définition de y, la propriété (4) du lemme est vérifiée. Quant à la propriété (2), elle résulte des choix de i et j.

Il faut bien saisir que le lemme ne donne qu'une condition nécessaire. La contraposée de ce lemme nous dit donc qu'un langage ne vérifiant pas les propriétés énoncées n'est pas rationnel, mais en aucun cas on ne peut affirmer qu'un langage non rationnel ne vérifiera pas ces propriétés. Il s'agit d'un problème d'implication logique, entre autres :

• Si le lemme est faux pour un langage donné, alors ce langage n'est pas rationnel
• Si le lemme est vrai pour un langage donné, alors ce langage peut ne pas être rationnel

Par exemple, notons u l'image miroir d'un mot quelconque u. u est donc tel que u**u est un palindrome. Le langage $L=\{u{u}^{R}v,u,v\in \{a,b{\}}^{+}\}$ n'est pas rationnel et vérifie le lemme. Plus explicitement, L est le langage des mots constitués d'un palindrome non vide suivi d'un mot non vide sur l'alphabet {a,b}.
Prenons p = 4, et w = uuv de longueur au moins 4. Si u est de longueur 1, alors v est de longueur au moins 2, et on choisit pour y la première lettre de v par exemple. Sinon, u est de longueur au moins 2 et on prend pour y la première lettre de u, z les lettres restantes et x le mot vide : on remarque que pour $k⩾2,y^k$ commence par le palindrome non vide yy.