Lemme de l'étoile

En théorie des langages, le lemme de l'étoile ou lemme d'itération pour les langages rationnels (ou encore lemme de gonflement, lemme de pompage, lemme de la pompe, 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'une partie centrale 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 la partie centrale est située suffisamment 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 qu'un langage est rationnel. En effet, il énonce une condition, nécessaire certes, mais non suffisante, de rationalité. Considérons le langage des mots qui commencent par un certain nombre de , suivi par le même nombre de . Il s'agit du langage composé des mots suivants : (mot vide) ab aabb aaabbb aaaabbbb aaaaabbbbb Nous allons montrer que ce langage n'est pas rationnel, i.e. il n'est pas représenté par une expression rationnelle (ou expression régulière). Pour cela, supposons par l'absurde que ce langage est rationnel. On peut alors appliquer le lemme de l'étoile sur un mot suffisamment long du langage. Par exemple : aaaaaaaaaabbbbbbbbbb Le lemme dit que l'on peut effacer ou répéter une partie du mot, qui est suffisamment près du début du mot. Cette partie sera donc composée que de a et est représentée en gras, par exemple : aaaaaaaaaabbbbbbbbbb Le lemme stipule donc que les mots suivants sont aussi dans le langage : aaaaaaabbbbbbbbbb (suppression de la partie, zéro copie) aaaaaaaaaabbbbbbbbbb (mot initial, une copie) aaaaaaaaaaaaabbbbbbbbbb (répétée une fois, deux copies) aaaaaaaaaaaaaaaabbbbbbbbbb (répétée deux fois, trois copies) aaaaaaaaaaaaaaaaaaabbbbbbbbbb (répétée trois fois, quatre copies) ce qui n'est pas vrai puisque l'on a pas le même nombre de a que de b.