Lemme de l'étoile

Carte Commune · n° 218089

En théorie des langages, le lemme de l'étoile ou lemme d'itération[réf. nécessaire] pour les langages rationnels (ou encore lemme de gonflement[réf. nécessaire], lemme de pompage[réf. nécessaire], lemme de la pompe[réf. nécessaire], 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'un facteur du mot peut être répétée un nombre quelconque de fois, et que chacun des mots produits est encore dans le langage. On peut même supposer que le facteur est situé suffisamment[pas clair] au début du mot. 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...

Lire sur Wikipédia