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

Idée de preuve : Si ${\displaystyle s}$ est assez long, son arbre de dérivation dans une grammaire context-free contient deux occurrence d'une ${\displaystyle N}$ un même chemin dans l'arbre. En répétant ${\displaystyle n}$ fois la partie de la dérivation ${\displaystyle N}$ ⇒...⇒ ${\displaystyle vNx}$ on obtient une dérivation pour ${\displaystyle uv^{n}wx^{n}y}$ (montrée pour ${\displaystyle n=0}$ et ${\displaystyle =n=2}$).

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 ${\displaystyle N}$ est l'« entier d'itération » ou la « constante d'itération », le couple ${\displaystyle (u,v)}$ ou la factorisation ${\displaystyle (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 ${\displaystyle (x,u,y,v,z)}$ peut être choisie grammaticale. Cette variante est bien utile dans certains cas. Voici l'énoncé :

Dans cet énoncé, le mot ${\displaystyle w}$ 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 ${\displaystyle S}$, qu'ils contiennent ou non des variables.

Prouvons que le langage

${\displaystyle L=\{a^{n}b^{n}c^{n}|n>0\}}$

n'est pas algébrique. Supposons le contraire, et soit ${\displaystyle N}$ la constante d'itération du langage. Considérons le mot ${\displaystyle w=a^{N}b^{N}c^{N}}$. Il existe une factorisation ${\displaystyle w=xuyvz}$ vérifiant les propriétés du lemme. Comme ${\displaystyle xu^{n}yv^{n}z\in L}$ pour tout ${\displaystyle n}$, chaque mot ${\displaystyle u^{n}v^{n}}$ contient le même nombre de lettres ${\displaystyle a,b}$ et ${\displaystyle c}$, et ce nombre est non nul. Or ceci est impossible si les lettres ${\displaystyle a}$ doivent précéder les lettres ${\displaystyle b}$ et celles-ci les lettres ${\displaystyle c}$.

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).

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.

• 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

• Olivier Carton, Langages formels, calculabilité et complexité, 2008 [détail de l’édition] (lire en ligne)

• (en) Michael Sipser, Introduction to the Theory of Computation, Boston, PWS Publishing, 1997, 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.

• Lemme d'itération pour les langages rationnels

• Portail de l'informatique théorique