Le Lemme de Pompage pour les Langages Réguliers

1. La Limite de la Mémoire Finie

Intuitivement, un automate fini déterministe (AFD) ne dispose que d'une mémoire finie, matérialisée par son nombre fini d'états. Il ne peut donc pas "compter" indéfiniment. Par exemple, pour reconnaître le langage $L=\{0^k{1}^k\mid k\ge 0\}$, un automate devrait se souvenir du nombre exact de 0 lus pour le comparer au nombre de 1. Si ce nombre peut être arbitrairement grand, un nombre fini d'états ne peut suffire.

Le lemme de pompage formalise cette intuition. Il stipule que si un automate avec $n$ états accepte un mot de longueur supérieure ou égale à $n$, le chemin d'acceptation dans l'automate doit nécessairement contenir un cycle (une boucle). C'est une application directe du principe des tiroirs de Dirichlet : si l'on traite $m\ge n+1$ symboles, on visite $m$ états, donc au moins un état doit être visité plus d'une fois.

Cette boucle peut alors être "pompée" : on peut la parcourir 0 fois, 1 fois, 2 fois, etc., générant ainsi une infinité de nouveaux mots qui doivent tous être acceptés par l'automate.

La vidéo suivante explique de manière très visuelle et en français comment l'existence de cette boucle est inévitable.

2. Énoncé Formel du Lemme de Pompage

La difficulté du lemme ne réside pas tant dans son intuition que dans la précision de son énoncé formel, qui implique une alternance de quantificateurs.

Lemme 5.1 (Lemme de pompage pour les langages réguliers)
Soit $A$ un langage régulier. Il existe un entier $n\ge 1$ (appelé "longueur de pompage") tel que pour tout mot $w\in A$ avec $|w|\ge n$, il existe une décomposition $w=xyz$ satisfaisant les trois conditions suivantes :

1. $y\ne ϵ$ (la partie pompée n'est pas vide).
2. $|xy|\le n$ (la boucle se situe dans les $n$ premiers symboles du mot).
3. Pour tout entier $i\ge 0$, le mot $x{y}^{i}z$ est dans $A$.

Ce document de l'Université de Waterloo est une référence écrite exemplaire pour l'énoncé et la preuve formelle.

3. Utilisation du Lemme : La Preuve par Contradiction

Le lemme de pompage est presque exclusivement utilisé pour prouver qu'un langage n'est pas régulier, via une preuve par l'absurde. La structure de la preuve peut être vue comme un jeu contradictoire :

1. Hypothèse : On suppose que le langage $L$ que l'on veut prouver non-régulier est régulier.
2. Affirmation du lemme : Puisque $L$ est supposé régulier, il doit satisfaire le lemme de pompage. Il existe donc une longueur de pompage $n$. Vous ne connaissez pas $n$, vous savez seulement qu'il existe.
3. Choix stratégique du mot : C'est l'étape la plus créative. Vous devez choisir un mot spécifique $w\in L$ dont la longueur dépend de $n$ (par exemple, $w=0^n{1}^n$) et qui est "fragile" à la décomposition. Votre choix doit être suffisamment malin pour que, peu importe comment l'adversaire décompose $w$, la structure du mot soit cassée par le pompage.
4. Analyse de la décomposition : Le lemme garantit qu'il existe une décomposition $w=xyz$ avec $y\ne ϵ$ et $|xy|\le n$. La condition $|xy|\le n$ est souvent la clé : elle contraint la nature de $y$. Par exemple, pour $w=0^n{1}^n$, elle implique que $y$ ne peut contenir que des 0.
5. Contradiction : Vous choisissez une valeur de $i$ (souvent $i=0$ pour "pomper à vide" ou $i=2$ pour dupliquer) et montrez que le mot résultant $x{y}^{i}z$ n'appartient pas à $L$.
6. Conclusion : Ceci contredit la condition 3 du lemme. L'hypothèse de départ (que $L$ est régulier) est donc fausse.

Exemple Canonique : $L=\{0^k{1}^k\mid k\ge 0\}$

La vidéo suivante de Michael Sipser (auteur de l'un de vos ouvrages de référence) applique cette méthode de manière exemplaire.

4. Exercice d'Application

Appliquons cette méthode à un autre langage classique.
Prouvez que le langage $PAL=\{w\in \{0,1{\}}^{\ast }\mid w=w^R\}$ (les palindromes) n'est pas régulier.

1. Hypothèse : Supposons que $PAL$ est régulier. Il existe donc une longueur de pompage $n$.
2. Choix du mot : Choisissons un palindrome dont la structure dépend de $n$ et qui place un "marqueur" au-delà de la zone de pompage initiale. Un excellent candidat est $w=0^{n}10^n$. Ce mot est bien dans $PAL$ et sa longueur $2n+1$ est supérieure à $n$.
3. Analyse de la décomposition :
   • Le lemme garantit que $w$ peut être écrit $w=xyz$.
   • Les conditions sont : $y\ne ϵ$ et $|xy|\le n$.
   • Puisque $|xy|\le n$, la sous-chaîne $xy$ est entièrement contenue dans le préfixe $0^n$. Par conséquent, $x$ et $y$ ne sont composés que de 0.
   • On peut donc écrire $x=0^a$, $y=0^b$, $z=0^{n-a-b}10^n$, avec $b\ge 1$ (car $y\ne ϵ$).
4. Contradiction :
   • Le lemme affirme que $x{y}^{i}z\in PAL$ pour tout $i\ge 0$.
   • Choisissons $i=2$. Le nouveau mot est $w^{\prime }=x{y}^{2}z=0^a{0}^b{0}^b{0}^{n-a-b}10^n=0^{n+b}10^n$.
   • Puisque $b\ge 1$, le nombre de 0 avant le 1 est différent du nombre de 0 après le 1. Le mot $w^{\prime }$ n'est donc pas un palindrome.
5. Conclusion : Nous avons trouvé un mot $x{y}^{2}z$ qui n'est pas dans $PAL$, ce qui contredit le lemme. Notre hypothèse initiale est donc fausse : $PAL$ n'est pas un langage régulier.

Vous pouvez retrouver ce même raisonnement dans la section 2 du document de Waterloo (LINK, page 52, Proposition 5.7).

5. Une Technique Alternative : Utiliser les Propriétés de Clôture

Parfois, une preuve plus élégante peut être construite en combinant le lemme de pompage avec les propriétés de clôture des langages réguliers (union, intersection, complément, etc.).

Par exemple, pour prouver que $EQ=\{w\mid \text{le nombre de 0 est eˊgal au nombre de 1}\}$ n'est pas régulier :

1. Supposons par l'absurde que $EQ$ est régulier.
2. Le langage $L^{\prime }=0^{\ast }{1}^{\ast }$ est clairement régulier (décrit par l'expression régulière 0*1*).
3. Nous savons que la classe des langages réguliers est close par intersection. Donc, si $EQ$ et $L^{\prime }$ sont réguliers, $EQ\cap L^{\prime }$ doit aussi être régulier.
4. Or, $EQ\cap L^{\prime }=\{0^k{1}^k\mid k\ge 0\}$.
5. Nous avons déjà prouvé (ou nous pouvons prouver avec le lemme) que $\{0^k{1}^k\}$ n'est pas régulier. C'est une contradiction.
6. Donc, l'hypothèse que $EQ$ est régulier est fausse.

Cette technique est très puissante et témoigne d'une compréhension profonde des propriétés de la classe des langages réguliers. Le professeur Sipser l'aborde à la fin de sa vidéo (LINK, à partir de 58:29).

Conclusion

Cette leçon vous a armé d'un outil fondamental pour analyser les limites des automates finis.

Points clés à retenir :

• Le lemme de pompage est une conséquence directe du nombre fini d'états d'un automate. Tout mot suffisamment long force une boucle.
• Son énoncé formel est précis, et la condition $|xy|\le n$ est souvent la clé pour restreindre les décompositions possibles.
• La méthode d'utilisation est une preuve par l'absurde structurée comme un jeu : vous choisissez un mot "intelligent" en fonction de $n$, puis vous montrez que, quelle que soit la décomposition, le pompage mène à une contradiction.
• Les propriétés de clôture peuvent offrir une voie de preuve alternative élégante en réduisant un problème à un cas déjà connu.

Nous avons maintenant atteint la limite expressive des langages réguliers. Dans notre prochain module, nous explorerons des modèles de calcul plus puissants capables de gérer des structures plus complexes, comme la correspondance de parenthèses ou les langages de programmation. Nous commencerons par définir les grammaires hors-contexte et les automates à pile, qui forment la base de l'analyse syntaxique.