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

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.

Summarize Timeline Fact Check

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 ${\displaystyle w}$ appartenant au langage, en choisissant les puissances des symboles de l'alphabet comme étant égales à la constante d'itération ${\displaystyle N}$. En effet, comme ${\displaystyle |uyv|\leq N}$, il devient alors impossible pour ${\displaystyle u}$ et ${\displaystyle v}$ de contenir les trois symboles dont la puissance peut varier. (Un langage algébrique, de manière générale, est un langage où il n'existe que des dépendances maximum deux à deux entre les puissances de symboles.)