Le matériel de cette page est repris de [Sak03]).
Sous l'intitulé lemme de l'étoile sont regroupés en fait plusieurs lemmes. Ces lemmes, appelés aussi lemmes de pompage ou lemmes d'itération, énoncent des propriétés simples des langages rationnels. Leur principal intérêt est de permettre de montrer que certains langages ne sont pas rationnels car ils violent une des propriétés énoncées.
Lemme 1. Pour tout langage rationnel L, il existe un entier n tel que tout mot f de longueur supérieur à n se factorise f = uvw où le xuv*wy est inclus dans L.
On montre facilement que le langage L = { anbn | n ≥ 0 } ne satisfait pas la propriété du lemme ci-dessus. On en déduit qu'il n'est pas rationnel. Par contre le langage L' = L + A*baA* satisfait la propriété bien qu'il ne soit pas rationnel.
Lemme 2. Pour tout langage rationnel L, il existe un entier n tel que pour tout mot f = xyz où y est de longueur supérieur à n, le mot y se factorise y = uvw de telle sorte que uv*w est inclus dans L.
Lemme 3. Pour tout langage rationnel L, il existe un entier n tel que pour tout mot f = xu1…uny où les mots ui sont non vides, il existe deux entiers 0 ≤ i < j ≤ n tel que xu1…ui(ui+1…uj)*uj+1…uny est inclus dans L.
On établit ici une réciproque au lemme de l'étoile. On définit d'abord deux propriétés des langages Hh et H'h. Ces deux propriétés sont des généralisations du lemme de l'étoile qui prennent en compte le complémentaire. En effet, les propriétés énoncées par les lemmes ci-dessus ne passent pas au complémentaire alors que le complémentaire d'un langage rationnel est encore rationnel. En revanche, les propriétés Hh et H'h restent vérifiées par passage au complémentaire. Le théorème d'Ehrenfeucht & co énonce que chacune des propriétés Hh et H'h caractérise les langages rationnels.
Soit h un entier. On dit qu'un langage L ⊆ A* satisfait la propriété Hh si pour toute factorisation f = xu1…uhy où les mots ui sont non vides, il existe deux entiers 0 ≤ i < j ≤ h tels que
f ∈ L ⇔ xu1…uiuj+1…uhy ∈ L
Soit h un entier. On dit qu'un langage L ⊆ A* satisfait la propriété H'h si pour toute factorisation f = xu1…uhy où les mots ui sont non vides, il existe deux entiers 0 ≤ i < j ≤ h tels que
∀ n ≥ 0 f ∈ L ⇔ xu1…ui(ui+1…uj)nuj+1…uhy ∈ L
Théorème (Ehrenfeucht, Parikh & Rozenberg). Pour tout
langage L, les propriétés suivantes sont équivalentes.
Il est évident que la propriété (1) implique la propriété (2) et que la propriété (2) implique la propriété (3). Pour montrer le théorème, il reste à montrer que la propriété (3) implique la propriété (1). La preuve de cette implication se fait en deux étapes. Dans un premier temps, on montre que si L satisfait H'h, alors u-1L satisfait aussi Hh pour tout mot u. Dans un deuxième temps, on montre que le nombre de langages vérifiant Hh est fini. En combinant les deux résultats, on obtient qu'un langage vérifiant Hh a un nombre fini de quotients à gauche et qu'il est donc rationnel.
La seconde étape de cette dernière implication nécessite le théorème de Ramsey. Pour un entier k et un ensemble E, on note Pk(E) l'ensemble des parties à k éléments de E. Pour un sous-ensemble F de E, Pk(F) s'identifie à un sous-ensemble de Pk(E). On pourra conculter [VLW92] pour une preuve du théorème suivant.
Théorème (Ramsey). Pour tout entier k (taille des parties), tout entier m (nombre de classes), et tout entier r, il existe un entier N(k, m, r) tel que pour toute partition en au plus m classes de Pk(E) d'un ensemble E d'au moins N éléments, il existe un sous-ensemble F de E d'au moins r éléments tel que Pk(F) est entièrement contenu dans une des classes de la partition.
On montre d'abord que si L satisfait H'h, alors u-1L satisfait aussi Hh. On suppose l'entier h et mot u fixés. Soit f un mot ayant une factorisation f = xu1…uhy où les mots ui sont non vides. Le mot f appartient à u-1L ssi uf appartient à L. En appliquant la propriété Hh à la factorisation uxu1…uhy, on obtient l'existence de deux entiers 0 ≤ i < j ≤ h qui donne la propriété requise.
On montre maintenant que nombre de langages vérifiant Hh est fini. En appliquant le théorème de Ramsey avec k = 2, m = 2 et r = h+1, on obtient un entier N = N(2, 2, h+1). On montre alors que si deux langages K et L vérifiant Hh coïncident sur les mots de longueur inférieure à N, alors K = L. On suppose donc que K et L satisfont Hh et que K ∩ A≤N = L ∩ A≤N où A≤n = (ε + A)n note l'ensemble des mots de longueur inférieure ou égale à n. On montre alors par récurrence sur la longueur de f que f ∈ K ssi f ∈ L. Pour f de longueur inférieure à N, le résultat découle directement des hypothèses. On suppose donc que f = a0…aNf' où les ai sont les N+1 premières lettres de f. Pour deux entiers 0 ≤ i < j ≤ N, on note fi,j le mot a0…ai-1aj…aNf' obtenu en supprimant le bloc ai…aj-1 de f. Puisque chaque mot fi,j est de longueur strictement inférieure, on fi,j ∈ K ssi fi,j ∈ L
On définit alors l'ensemble X.
X = { (i, j) | fi,j ∈ L }
On considère l'ensemble E = {0, …, N} et la partition de P2(E) ayant X et son complémentaire comme classes. Par le théorème de Ramsey, il existe h+1 entiers k0 < k1 < … < kh, tels qu'une des deux alternatives suivantes soit vraie.
Dans les deus cas, on a fki,kj ∈ L ssi fki',kj' ∈ L pour toutes paires (i, j) et (i', j') d'entiers.
Les entiers k0 < k1 < … < kh definissent une factorisation de f. On pose x = a0…ak0-1 et ui = aki-1…aki-1 pour 1 ≤ i ≤ h et z = akh…aNf'. On a alors une factorisation f = xu1…uhy où les mots ui sont non vides. On note que le mot xu1…uiuj+1…uhy est en fait le mot noté fki,kj. Comme K satisfait Hh, il existe deux autres entiers i et j tels que f ∈ K ssi fki,kj ∈ K. Comme L satisfait aussi Hh, il existe deux entiers i' et j' tels que f ∈ L ssi fki',kj' ∈ L. En combinant toutes les équivalences, on obtient finalement f ∈ K ssi f ∈ L, ce qui achève la preuve que K et L sont égaux.