Lemme d'itération 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 

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é :

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 

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

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 
 

 

  Section 1.4: Nonregular Languages, pp. 77–83. Section 2.3: Non-context-free Languages, pp. 115–119.

Voir aussi 
 Lemme d'itération pour les langages rationnels

Langage formel