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

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 | modifier le code]

Lemme d'itération — Soit L un langage algébrique. Il existe un entier N tel que tout mot w de L de longueur |w|\ge N possède une factorisation w=xuyvz telle que

  1.  0<|uv|, |uyv|\le N et
  2. xu^nyv^nz \in L pour tout entier n\ge0.

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 N est l'« entier d'itération », le couple (u,v) ou la factorisation (x,u,y,v,z) est une « paire itérante ».

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

Lemme d'itération (variante grammaticale) — Soit G une grammaire algébrique d'axiome S. Il existe un entier N tel que tout mot w qui dérive de S de longueur |w|\ge N possède une factorisation w=xuyvz telle que

  1.  0<|uv|, |uyv|\le N et
  2. il existe une variable X telle que S\xrightarrow* xXz, X\xrightarrow* uXv, X\xrightarrow* y.

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

Exemple d'utilisation du lemme[modifier | modifier le code]

Prouvons que le langage L = \lbrace a^nb^nc^n|n>0\rbrace n'est pas algébrique. Supposons le contraire, et soit N la constante d'itération du langage. Considérons le mot w=a^Nb^Nc^N. Il existe une factorisation w=xuyvz vérifiant les propriétés du lemme. Comme xu^nyv^nz \in L pour tout n, chaque mot u^nv^n contient le même nombre de lettres a,b et c, et ce nombre est non nul. Or ceci est impossible si les lettres a doivent précéder les lettres b et celles-ci les lettres c.

Limitations[modifier | modifier le code]

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 | modifier le code]

  • 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,‎ 1961, p. 143-172
  • (en) Michael Sipser, Introduction to the Theory of Computation, Boston, PWS Publishing,‎ 1997 (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 | modifier le code]