Lemme de l'étoile

En théorie des langages, le lemme de l'étoile (ou encore lemme d'itération, 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.

Le lemme de l'étoile a été formulé pour la première fois en 1961 par Y. Bar-Hillel, Micha A. Perles, Eli Shamir[1]. 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é.

Énoncé formelModifier

Lemme de l'étoile — Soit   un langage rationnel. Il existe un entier   tel que tout mot   de   de longueur   possède une factorisation   telle que

  1.   et
  2.   pour tout entier    .

Ici,   dénote la longueur du mot  . L'entier   ne dépend que de   et non pas du mot   choisi. Il est parfois appelé « constante d'itération ». Le facteur central   de la factorisation   est appelé un « facteur itérant ». Le nom « lemme de l'étoile » provient de la formulation équivalente suivante de la conclusion du lemme :

 .

Parmi les itérés   qui sont dans le langage figure aussi le mot   obtenu pour  .

Il existe de nombreuses variantes de ce lemme ; la plus fréquente stipule, au lieu de la condition  , la condition  , et donc que le facteur itérant   se situe près du début du mot.

Un exemple d'application du lemme de l'étoileModifier

Le lemme de l'étoile est souvent utilisé pour démontrer qu'un langage donné n'est pas rationnel. La preuve se fait en général par l'absurde, en supposant que le langage est rationnel et en exhibant un mot du langage qui ne vérifie pas la conclusion du lemme.

Prenons par exemple le langage   sur l'alphabet  . Supposons par l'absurde que   est rationnel. Soit   la constante d'itération de  . On choisit le mot  . Par le lemme, il existe un mot   vérifiant les conditions du lemme de l'étoile. En particulier, et en utilisant la variante énoncée, on a  , et donc   et   sont composés uniquement de lettres  . Posons  . On a  . Alors   pour tout entier  . Comme ces mots devraient être dans   on devrait avoir   pour tout entier   et donc  , ce qui est en contradiction avec l'hypothèse. Donc   n'est pas rationnel.

On montre de même que

  • le langage des palindromes sur   n'est pas rationnel,
  • le langage   sur   (où   désigne le nombre d'occurrences de la lettre   dans le mot  ) est composé des mots qui ont autant de   que de  . Il n'est pas rationnel.

Un peu plus compliqué est la preuve que le langage   n'est pas rationnel. De même, le langage   n'est pas rationnel. Au lieu de faire une preuve directe, il vaut mieux passer par le langage complément.

Preuve du lemme de l'étoileModifier

L'argument principal de la preuve est le principe des tiroirs. Il s’emploie, dans le cas présent, sous la forme du constat qu'un chemin assez long dans un graphe fini passe deux fois par le même sommet.

Soit   un langage rationnel, sur un alphabet  . Par le théorème de Kleene, il existe un automate fini   qui reconnaît  . Soit   le nombre d'états de cet automate.

Soit   un mot de   de longueur  . Comme   est dans  , il est reconnu par  , et il existe un chemin réussi   de l'état initial noté ici   vers un état terminal   d'étiquette  . Soient   les   premières lettres de  , posons  , et soient   les états successifs atteints après la lecture de ces lettres. On a alors le chemin suivant :

 

Le principe des tiroirs dit que, parmi les   états  , deux sont égaux. Il existe donc deux entiers   avec   tels que  . Posons   et

 

Le chemin d'étiquette   se factorise de la façon suivante :

 

Il en résulte que   pour tout entier  , et donc que   est dans   pour tout entier  . Enfin, on a  , donc  . Ceci prouve le lemme.

La preuve montre en fait la variante du lemme énoncée ci-dessus, à savoir que de plus, on a  , puisque  .

Le lemme est une condition nécessaire mais non suffisante de rationalitéModifier

Le lemme ne donne qu'une condition nécessaire pour qu'un langage soit rationnel. Voici un exemple d'un langage non rationnel qui vérifie le lemme de l'étoile dans la version donnée ci-dessus.

Notons   l'image miroir d'un mot  , et soit   l'ensemble des mots qui ont un préfixe qui est un palindrome non vide de longueur paire.

Posons  , et soit   un mot de longueur au moins 4 du langage. Si   est une lettre, la factorisation   avec  ,   la première lettre de   et   le reste du mot convient. Si   est de longueur au moins 2, on choisit pour   le mot vide, pour   la première lettre de  , et pour   le   reste du mot. Pour  , le mot   commence par le palindrome non vide  ; pour  , le mot   commence par le palindrome formé de   privé de sa première lettre, suivi de l'image miroir de ce suffixe (lui-même suivi de la première lettre de  ).

ExtensionsModifier

Il existe de nombreuses variantes du lemme de l'étoile, plus ou moins sophistiquées, pour prendre en compte des langages plus compliqués.

Choix du facteur itérantModifier

La première variante énonce que la place du facteur itérant peut être choisie dans n'importe quelle plage du mot de longueur assez grande. Voici l'énoncé:

Lemme de l'étoile (variante) — Soit   un langage rationnel. Il existe un entier   tel que pour tout mot   de  , et pour toute factorisation  , avec   de longueur  , il existe une factorisation   telle que

  1.   et
  2.  .

Exemple d'utilisation du choix du facteur itérantModifier

Sur l'alphabet  , en posant, pour tout mot   sur cet alphabet:   et  , respectivement le nombre de   et le nombre de   dans  ,  on a que l'ensemble des mots   tels que   vérifie la conclusion du lemme de l'étoile (en prenant  , il existe, dans tous mots de cet ensemble, un   et un   se suivant; il est possible d'itérer cette partie du mot en restant dans ce langage: par exemple, si le mot est de la forme   (le cas   étant similaire), on a que, pour tout entier naturel n,   est également dans le langage). Cependant, il ne respecte pas le lemme de l'étoile par blocs: par l'absurde, on suppose disposer d'un tel  . On pose alors:   et  ,   et  , le mot vide. On dispose alors d'une factorisation de la forme:   respectant la conclusion du choix du facteur itérant. Or:   et  , ce qui est absurde.

Preuve du lemme avec choix du facteur itérantModifier

Le schéma de la preuve est semblable à celui du premier lemme de l'étoile énoncé. Soit   un langage rationnel, sur un alphabet  , soit  , un automate fini reconnaissant   et soit   son nombre d'états. Soit   un mot de  , et soit  , une factorisation de ce mot telle que  . On pose   où les   sont des lettres et où   le suffixe de   la longueur  . Il existe une suite   d'états, où   est initial et   est terminal, tels que

 ,   et  .

Par le principe des tiroirs, il existe deux entiers   tels que  . Posons

 ,  ,  .

Alors

  et de plus  

pour tout entier naturel  . L'automate reconnaît donc tous les mots de la forme  , et de plus  .

Lemme de l'étoile par blocsModifier

Dans cette variante, on découpe le mot en blocs, et c'est un groupe de blocs que l'on peut itérer:

Lemme de l'étoile par blocs — Soit   un langage rationnel. Il existe un entier   tel que pour tout mot   de  , et pour toute factorisation  , où tous les   sont non vides, il existe deux entiers   avec

  1.   et
  2.  .

Dans cet énoncé et les suivants, on convient que   est égal au mot vide si  , et de même   est égal au mot vide si  .

Preuve du lemme de l'étoile par blocsModifier

Soit   un langage rationnel. Par théorème de Kleene, il existe un automate fini   reconnaissant  . Soit   le nombre d'états de   et soit   un mot de   Il existe une suite d'états   tels que

 ,

  est initial et   est terminal. Par le principe des tiroirs, il existe deux indice   tels que  . On a donc, en notant   cet état et  , que

 

dans l'automate. On en déduit le résultat souhaité : pour tout entier naturel  , le mot  est un mot accepté par l'automate et est donc un mot de  .

Contre-exemple à la réciproque du lemme de l'étoile par blocsModifier

La réciproque de ce lemme est fausse (il ne s'agit donc pas d'une condition nécessaire et suffisante). Un exemple est donné ci-dessous.

Soient   et   ; soit   et  . Le langage   défini par:

 

vérifie la conclusion du lemme de l'étoile par blocs. Cependant, il n'est pas rationnel[2].

Lemme de l'étoile à la OgdenModifier

Le lemme d'Ogden[3], initialement conçu pour les langages algébriques, s'applique aussi bien aux langages rationnels. Étant donné un mot  , où les   sont des lettres, on appelle position dans   tout entier de l'ensemble  . Un choix de   positions distinguées dans   (ceci est la terminologie habituelle, un peu alambiquée) est simplement un sous-ensemble   de positions contenant   éléments. Avec ces définitions, le lemme s'énonce comme suit:

Lemme de l'étoile à la Ogden — Soit   un langage rationnel. Il existe un entier   tel que pour tout mot   de   de longueur  , et pour tout choix de   positions distinguées dans  , il existe une factorisation   telle que

  1.   contient au moins une et au plus   positions distinguées
  2.  .

Si l'on distingue toutes les positions dans  , on retrouve le lemme de l'étoile initial. Si l'on considère la factorisation de   obtenue en segmentant le mot après chaque position distinguée, on obtient essentiellement le lemme de l'étoile par blocs. Les preuves de ces énoncés sont très similaires.

Conditions nécessaires et suffisantesModifier

En exploitant les propriétés de clôture et de finitude associées aux langages rationnels, on peut obtenir, en partant du lemme de l’étoile, une forme du lemme de l’étoile qui est caractéristique des langages rationnels.

Théorème de JaffeModifier

Une première caractérisation, qui se fonde sur un renforcement du lemme de l'étoile « faible » est celle de J. Jaffe[4].

On dit qu'un langage   satisfait la condition   pour un certain entier naturel   si pour tout mot   de longueur  , il existe une factorisation   avec   non vide telle que:  

On dit qu'un langage   satisfait la condition   pour un certain entier naturel   si pour tout mot   de longueur  , il existe une factorisation   avec   non vide telle que:  

On a alors le théorème de Jaffe:

Théorème de Jaffe — Soit   un langage. Les conditions suivantes sont équivalentes :

  1.   est rationnel ;
  2. Il existe un entier   tel que   vérifie la condition   ;
  3. Il existe un entier   tel que   vérifie la condition  .

Elle est cependant « non-locale » puisque pour chaque mot, il faut trouver une factorisation qui marche uniformément par rapport à tous les quotients à droite de ce mot.

Théorème d'Ehrenfeucht, Parikh et RozenbergModifier

Un théorème prouvé par Andrzej Ehrenfeucht, Rohit Jivanlal Parikh et Grzegorz Rozenberg[5] donne une condition, fondée sur un renforcement du lemme de l'étoile par blocs, qui est nécessaire et suffisante pour qu'un langage soit rationnel et qui est « locale » au sens précédent.

On dit qu'un langage   sur l'alphabet   vérifie la condition   pour un entier   si pour tout mot  , et pour toute factorisation  , où les mots   sont non vides, il existe deux indices   avec   tels que

  pour tout  .

L'équivalence équivaut à la conjonction des deux implications :

  et
 .

On dit que   vérifie la condition   si pour tout mot  , et pour toute factorisation  , où les mots   sont non vides, il existe deux indices   avec   tels que

 .

Théorème d'Ehrenfeucht, Parikh et Rozenberg — Soit   un langage. Les conditions suivantes sont équivalentes :

  1.   est rationnel ;
  2. il existe un entier   tel que   vérifie la condition   ;
  3. il existe un entier   tel que   vérifie la condition  .

Il convient de noter une différence importante avec le théorème de Jaffe énoncée précédemment. Les conditions   et   portent sur une factorisation d'un mot et de tous ses quotients à droite tandis que les conditions   et   portent sur toutes les factorisations possibles d'un seul mot, ce qui assure leur caractère local.

L'implication difficile est  . Elle utilise, à la place du principe des tiroirs, le théorème de Ramsey.

NotesModifier

RéférencesModifier

  • Yehoshua Bar-Hillel, Micha A. Perles et Eli Shamir, « On formal properties of simple phrase structure grammars », Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung, vol. 14,‎ , p. 143-172
  • William F. Ogden, « A Helpful Result for Proving Inherent Ambiguity », Mathematical Systems Theory, vol. 2, no 3,‎ , p. 191-194 (DOI 10.1007/BF01694004)

Voir aussiModifier