À quoi sert le lemme de pompage?

C'est quelque chose que je n'ai pas trouvé - mais j'ai toujours trouvé intéressant que le lemme de pompage soit juste un lemme (d'autant plus qu'il a le même nom pour les langues régulières, les langues sans contexte, etc ...)

Qu'est-ce qu'un lemme?

Dans l'article fondateur de Rabin et Scott, Automates finis et leurs problèmes de décision , le lemme de pompage apparaît comme un lemme (lemme 8) au résultat suivant (théorème 9):

La langue acceptée par un DFA à états est infinie si et seulement si elle accepte un mot dont la longueur est comprise entre et .$n$$n$$2n$

Le lemme de pompage implique la direction .$\Longrightarrow$

Il "donne également une autre preuve" que le langage n'est pas régulier (la preuve originale dans l'article utilise la théorie de Myhill-Nerode).$\{0^n 1 0^n : n \geq 0\}$