Lemme d'itération pour les langages algébriques

lemme donnant une condition de répétition nécessaire pour les langages algébriques

Le lemme d'itération pour les langages algébriques, aussi connu sous le vocable lemme de Bar-Hillel, Perles et Shamir, donne une condition de répétition nécessaire pour les langages algébriques. Sa version simplifiée pour les langages rationnels est le lemme de l'étoile.

Une version plus élaborée du lemme d'itération est le lemme d'Ogden.

Énoncé formel modifier

 
Idée de preuve : Si   est assez long, son arbre de dérivation dans une grammaire context-free contient deux occurrence d'une   un même chemin dans l'arbre. En répétant   fois la partie de la dérivation   ⇒...⇒   on obtient une dérivation pour   (montrée pour   et  ).

Lemme d'itération — Soit   un langage algébrique. Il existe un entier   tel que tout mot   de   de longueur   possède une factorisation   telle que :

  1.   ;
  2.   pour tout entier  .

Le lemme indique donc que, dans un langage algébrique, certains facteurs de mots assez longs peuvent être itérés de concert. L'entier   est l'« entier d'itération » ou la « constante d'itération », le couple   ou la factorisation   est une « paire itérante ».

Il existe une variante grammaticale du lemme d'itération : elle dit que la paire itérante   peut être choisie grammaticale. Cette variante est bien utile dans certains cas. Voici l'énoncé :

Lemme d'itération (variante grammaticale) — Soit   une grammaire algébrique d'axiome  . Il existe un entier   tel que tout mot   qui dérive de   de longueur   possède une factorisation   telle que :

  1.   ;
  2. il existe une variable   telle que  ,  ,  .

Dans cet énoncé, le mot   peut contenir des variables de la grammaire : il appartient au « langage élargi » de la grammaire qui est constitué, par définition, de tous les mots dérivant de  , qu'ils contiennent ou non des variables.

Exemple d'utilisation du lemme modifier

Prouvons que le langage

 

n'est pas algébrique. Supposons le contraire, et soit   la constante d'itération du langage. Considérons le mot  . Il existe une factorisation   vérifiant les propriétés du lemme. Comme   pour tout  , chaque mot   contient le même nombre de lettres   et  , et ce nombre est non nul. Or ceci est impossible si les lettres   doivent précéder les lettres   et celles-ci les lettres  .

Méthode générale modifier

La technique consiste à choisir un mot w appartenant au langage, et à choisir les puissances des symboles de l'alphabet comme étant égale à N. En effet, comme |vxy| < N, il devient alors impossible pour x et y de contenir les trois symboles dont la puissance peut varier. (Un langage algébrique, de manière générale, est un langage ou il n'existe que des dépendances maximum deux à deux entre les puissances de symboles).

Limitations modifier

Comme pour les langages rationnels, le lemme d'itération pour les langages algébriques est une condition nécessaire mais non suffisante. Parmi les lemmes de même nature, le lemme d'Ogden est bien plus puissant.

Références modifier

  • 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
  • (en) Michael Sipser, Introduction to the Theory of Computation, Boston, PWS Publishing, , 396 p. (ISBN 978-0-534-94728-6, LCCN 96035322) Section 1.4: Nonregular Languages, pp. 77–83. Section 2.3: Non-context-free Languages, pp. 115–119.

Voir aussi modifier