Une technique des langages formels donnant des conditions nécessaires pour qu'un langage soit régulier en montrant que des mots suffisamment longs se décomposent de sorte qu'un sous-mot central puisse être répété (pomper) un nombre arbitraire de fois et que les mots résultants restent dans le langage.

Principe

Un langage régulier est reconnu par un automate fini ; tout calcul acceptant sur une entrée suffisamment longue doit visiter un état deux fois, produisant une boucle dont la traversée répétée engendre infiniment de mots apparentés. Cette boucle implique une décomposition autorisant le pompage d'un bloc central.

Démonstration

Pour montrer que le langage {a^n b^n : n ≥ 0} n'est pas régulier, on suppose le contraire et on applique le lemme de pompage avec sa longueur de pompage ; toute décomposition exigée par le lemme conduit à des mots pompés ayant des nombres d'a et de b déséquilibrés, ce qui contredit l'appartenance et prouve la non-régularité.

Mauvaise application

Employer le lemme de pompage comme condition suffisante pour la régularité (alors qu'il n'est que nécessaire), ou choisir incorrectement une décomposition sans quantifier sur toutes les décompositions exigées par le lemme, sont des erreurs fréquentes qui invalident des démonstrations.

Conséquence

Fournit une méthode pratique pour prouver la non-régularité de langages et raisonner sur les limites des automates finis ; il éclaire pourquoi la mémoire finie empêche de gérer des dépendances non bornées.

Inversion

La réciproque est fausse : un langage qui satisfait la condition de pompage pour une longueur ou une décomposition particulière peut néanmoins être non régulier ; des outils plus fins (par exemple le théorème de Myhill–Nerode ou le lemme d'Ogden) sont nécessaires pour des distinctions plus précises.

Limite

Ne s'applique qu'aux langages réguliers et, via propriétés de fermeture, à certains compléments ; les langages hors-contexte ont leur propre version du lemme de pompage, et le lemme n'offre pas d'automate constructif lorsque les conditions échouent.

Tension sémantique

Il existe une tension entre le lemme de pompage et d'autres caractérisations de la régularité : Myhill–Nerode donne un critère nécessaire-et-suffisant basé sur une relation d'équivalence, tandis que le pompage n'est qu'une propriété structurelle nécessaire et peut rester non concluant dans des cas limites.

Synthèse

Le lemme de pompage formalise la limitation de mémoire finie des automates finis : tout mot accepté suffisamment long contient un segment cyclique répétable qui peut être pompé pour produire infiniment de mots acceptés, et la violation de cette propriété prouve la non-régularité.