Lemme de l'étoile
En théorie des langages, le lemme de l'étoile ou lemme d'itération[réf. nécessaire] pour les langages rationnels (ou encore lemme de gonflement[réf. nécessaire], lemme de pompage[réf. nécessaire], lemme de la pompe[réf. nécessaire], pumping lemma en anglais) énonce une propriété typique de tout langage rationnel. Informellement, il stipule que tout mot suffisamment long d'un langage rationnel peut être pompé, au sens qu'une partie centrale du mot peut être répétée un nombre quelconque de fois, et que chacun des mots produits est encore dans le langage. On peut même supposer que la partie centrale est située suffisamment[pas clair] au début du mot.
Le lemme de l'étoile a été formulé pour la première fois en 1961 par Y. Bar-Hillel, Micha A. Perles, Eli Shamir[1]. Le même article contient un lemme d'itération pour les langages algébriques.
Le lemme de l'étoile est couramment utilisé pour montrer qu'un langage donné n'est pas rationnel (en raisonnant par l'absurde). En revanche, il ne peut être employé pour démontrer qu'un langage est rationnel. En effet, il énonce une condition, nécessaire certes, mais non suffisante, de rationalité.
Explication informelle
[modifier | modifier le code]Considérons le langage des mots qui commencent par un certain nombre de , suivi par le même nombre de . Il s'agit du langage composé des mots suivants :
(mot vide) ab aabb aaabbb aaaabbbb aaaaabbbbb ...
Nous allons montrer que ce langage n'est pas rationnel, i.e. il n'est pas représenté par une expression rationnelle (ou expression régulière). Pour cela, supposons par l'absurde que ce langage est rationnel. On peut alors appliquer le lemme de l'étoile sur un mot suffisamment long du langage. Par exemple :
aaaaaaaaaabbbbbbbbbb
Le lemme dit que l'on peut effacer ou répéter une partie du mot, qui est suffisamment près du début du mot. Cette partie sera donc composée que de a et est représentée en gras, par exemple :
aaaaaaaaaabbbbbbbbbb
Le lemme stipule donc que les mots suivants sont aussi dans le langage :
aaaaaaabbbbbbbbbb (suppression de la partie, zéro copie) aaaaaaaaaabbbbbbbbbb (mot initial, une copie) aaaaaaaaaaaaabbbbbbbbbb (répétée une fois, deux copies) aaaaaaaaaaaaaaaabbbbbbbbbb (répétée deux fois, trois copies) aaaaaaaaaaaaaaaaaaabbbbbbbbbb (répétée trois fois, quatre copies) ...
ce qui n'est pas vrai puisque l'on a pas le même nombre de a que de b. Dans la suite, nous allons donner l'énoncé précis et formel du lemme de l'étoile. Puis la démonstration formelle de ce que l'on vient de voir.
Énoncé formel
[modifier | modifier le code]Dans l'énoncé suivant dénote la longueur du mot . On écrit pour dire que l'on a copies du mot . Pour n = 0, est le mot vide.
Théorème — Soit un langage rationnel. Il existe un entier tel que tout mot de de longueur possède une factorisation telle que
- et
- pour tout entier .
Dans l'énoncé, l'entier ne dépend que de et non pas du mot choisi. Il est parfois appelé constante d'itération[réf. nécessaire]. Le facteur central de la factorisation est appelé un facteur itérant[réf. nécessaire]. Le nom « lemme de l'étoile » provient de la formulation équivalente suivante de la conclusion du lemme, dans laquelle une étoile apparaît :
- .
Parmi les itérés qui sont dans le langage figure aussi le mot obtenu pour .
Il existe de nombreuses variantes de ce lemme ; la plus fréquente stipule, au lieu de la condition , la condition , et donc que le facteur itérant se situe près du début du mot.
Exemples d'application du lemme de l'étoile
[modifier | modifier le code]Le lemme de l'étoile est souvent utilisé pour démontrer qu'un langage donné n'est pas rationnel. La preuve se fait en général par l'absurde, en supposant que le langage est rationnel et en exhibant un mot du langage qui ne vérifie pas la conclusion du lemme.
Exemple d'une démonstration formelle
[modifier | modifier le code]Montrons que le langage sur l'alphabet n'est pas rationnel. Il s'agit du langage composé des mots qui commencent par un certain nombre de , suivi par le même nombre de . Il contient notamment le mot vide, ainsi que les mots , , , etc.
Supposons par l'absurde que est rationnel. Le lemme de l'étoile peut alors s'appliquer à ce langage.
Soit une constante d'itération de , et considérons le mot . Par le lemme de l'étoile, il existe un mot vérifiant les conditions du lemme de l'étoile. En particulier, et en utilisant la variante énoncée, on a , et donc et sont composés uniquement de lettres .
Posons maintenant , et remarquons que (car ) et . Alors, par le lemme de l'étoile, et pour tout , tous les mots appartiennent également au langage . Ainsi, on devrait avoir pour tout entier , et donc , ce qui est en contradiction avec l'hypothèse. Donc n'est pas rationnel.
D'autres cas d'applications
[modifier | modifier le code]On montre de même que
- le langage des palindromes sur n'est pas rationnel[réf. nécessaire],
- le langage sur (où désigne le nombre d'occurrences de la lettre dans le mot ) est composé des mots qui ont autant de que de . Il n'est pas rationnel[réf. nécessaire].
Un peu plus compliqué est la preuve que le langage n'est pas rationnel[réf. nécessaire]. De même, le langage n'est pas rationnel[réf. nécessaire]. Au lieu de faire une preuve directe, il vaut mieux passer par le langage complément.
Preuve du lemme de l'étoile
[modifier | modifier le code]L'argument principal de la preuve est le principe des tiroirs. Il s’emploie, dans le cas présent, sous la forme du constat qu'un chemin assez long dans un graphe fini passe deux fois par le même sommet.
Soit un langage rationnel, sur un alphabet . Par le théorème de Kleene, il existe un automate fini qui reconnaît . Soit le nombre d'états de cet automate. Soit un mot de de longueur . Comme est dans , il est reconnu par , et il existe un chemin acceptant de l'état initial noté ici vers un état terminal d'étiquette . Soient les premières lettres de , posons , et soient les états successifs atteints après la lecture de ces lettres. On a alors le chemin suivant :
Le principe des tiroirs dit que, parmi les états , deux d'entre eux sont égaux. Il existe donc deux entiers avec tels que . Posons et
Le chemin d'étiquette se factorise de la façon suivante :
Il en résulte que pour tout entier , et donc que est dans pour tout entier . Enfin, on a , donc . Ceci prouve le lemme.
La preuve montre en fait la variante du lemme énoncée ci-dessus, à savoir que de plus, on a , puisque .
Le lemme est une condition nécessaire mais non suffisante de rationalité
[modifier | modifier le code]Le lemme ne donne qu'une condition nécessaire pour qu'un langage soit rationnel.
- Un premier exemple
Voici un langage non rationnel qui vérifie le lemme de l'étoile dans la version donnée ci-dessus. Notons l'image miroir d'un mot , et soit l'ensemble des mots qui ont un préfixe qui est un palindrome non vide de longueur paire.
Posons , et soit un mot de longueur au moins 4 du langage. Si est une lettre, la factorisation avec , la première lettre de et le reste du mot convient. Si est de longueur au moins 2, on choisit pour le mot vide, pour la première lettre de , et pour le reste du mot. Pour , le mot commence par le palindrome non vide ; pour , le mot commence par le palindrome formé de privé de sa première lettre, suivi de l'image miroir de ce suffixe (lui-même suivi de la première lettre de ).
- Un autre exemple
Le langage n'est pas rationnel mais vérifie les conditions du lemme de l’étoile ; en effet, tout mot se factorise en , de manière que pour . Pour cela, on choisit pour la première lettre : c'est soit la lettre , et le nombre de est arbitraire, ou c'est un ou sans e tête, et le nombre de ou est arbitraire.
Extensions
[modifier | modifier le code]Il existe de nombreuses variantes du lemme de l'étoile, plus ou moins sophistiquées, pour prendre en compte des langages plus compliqués.
Choix du facteur itérant
[modifier | modifier le code]La première variante énonce que la place du facteur itérant peut être choisie dans n'importe quelle plage du mot de longueur assez grande. Voici l'énoncé :
Lemme de l'étoile (variante) — Soit un langage rationnel. Il existe un entier tel que pour tout mot de , et pour toute factorisation , avec de longueur , il existe une factorisation telle que
- et
- .
Exemple d'utilisation du choix du facteur itérant
[modifier | modifier le code]Sur l'alphabet , en posant, pour tout mot sur cet alphabet: et , respectivement le nombre de et le nombre de dans , on a que l'ensemble des mots tels que vérifie la conclusion du lemme de l'étoile (en prenant , il existe, dans tous mots de cet ensemble, un et un se suivant; il est possible d'itérer cette partie du mot en restant dans ce langage: par exemple, si le mot est de la forme (le cas étant similaire), on a que, pour tout entier naturel n, est également dans le langage). Cependant, il ne respecte pas le lemme de l'étoile par blocs: par l'absurde, on suppose disposer d'un tel . On pose alors: et , et , le mot vide. On dispose alors d'une factorisation de la forme: respectant la conclusion du choix du facteur itérant. Or: et , ce qui est absurde.
Preuve du lemme avec choix du facteur itérant
[modifier | modifier le code]Le schéma de la preuve est semblable à celui du premier lemme de l'étoile énoncé. Soit un langage rationnel, sur un alphabet , soit , un automate fini reconnaissant et soit son nombre d'états. Soit un mot de , et soit , une factorisation de ce mot telle que . On pose où les sont des lettres et où le suffixe de la longueur . Il existe une suite d'états, où est initial et est terminal, tels que
- , et .
Par le principe des tiroirs, il existe deux entiers tels que . Posons
- , , .
Alors
- et de plus
pour tout entier naturel . L'automate reconnaît donc tous les mots de la forme , et de plus .
Lemme de l'étoile par blocs
[modifier | modifier le code]Dans cette variante, on découpe le mot en blocs, et c'est un groupe de blocs que l'on peut itérer:
Lemme de l'étoile par blocs — Soit un langage rationnel. Il existe un entier tel que pour tout mot de , et pour toute factorisation , où tous les sont non vides, il existe deux entiers avec
- et
- .
Dans cet énoncé et les suivants, on convient que est égal au mot vide si , et de même est égal au mot vide si .
Preuve du lemme de l'étoile par blocs
[modifier | modifier le code]Soit un langage rationnel. Par théorème de Kleene, il existe un automate fini reconnaissant . Soit le nombre d'états de et soit un mot de Il existe une suite d'états tels que
- ,
où est initial et est terminal. Par le principe des tiroirs, il existe deux indice tels que . On a donc, en notant cet état et , que
dans l'automate. On en déduit le résultat souhaité : pour tout entier naturel , le mot est un mot accepté par l'automate et est donc un mot de .
Contre-exemple à la réciproque du lemme de l'étoile par blocs
[modifier | modifier le code]La réciproque de ce lemme est fausse (il ne s'agit donc pas d'une condition nécessaire et suffisante). Un exemple est donné ci-dessous.
Soient et ; soit et . Le langage défini par:
vérifie la conclusion du lemme de l'étoile par blocs. Cependant, il n'est pas rationnel[2].
Lemme de l'étoile à la Ogden
[modifier | modifier le code]Le lemme d'Ogden[3], initialement conçu pour les langages algébriques, s'applique aussi bien aux langages rationnels. Étant donné un mot , où les sont des lettres, on appelle position dans tout entier de l'ensemble . Un choix de positions distinguées dans (ceci est la terminologie habituelle, un peu alambiquée) est simplement un sous-ensemble de positions contenant éléments. Avec ces définitions, le lemme s'énonce comme suit:
Lemme de l'étoile à la Ogden — Soit un langage rationnel. Il existe un entier tel que pour tout mot de de longueur , et pour tout choix de positions distinguées dans , il existe une factorisation telle que
- contient au moins une et au plus positions distinguées
- .
Si l'on distingue toutes les positions dans , on retrouve le lemme de l'étoile initial. Si l'on considère la factorisation de obtenue en segmentant le mot après chaque position distinguée, on obtient essentiellement le lemme de l'étoile par blocs. Les preuves de ces énoncés sont très similaires.
Conditions nécessaires et suffisantes
[modifier | modifier le code]En exploitant les propriétés de clôture et de finitude associées aux langages rationnels, on peut obtenir, en partant du lemme de l’étoile, une forme du lemme de l’étoile qui est caractéristique des langages rationnels.
Théorème de Jaffe
[modifier | modifier le code]Une première caractérisation, qui se fonde sur un renforcement du lemme de l'étoile « faible » est celle de J. Jaffe[4].
On dit qu'un langage satisfait la condition pour un certain entier naturel si pour tout mot de longueur , il existe une factorisation avec non vide telle que:
On dit qu'un langage satisfait la condition pour un certain entier naturel si pour tout mot de longueur , il existe une factorisation avec non vide telle que:
On a alors le théorème de Jaffe:
Théorème de Jaffe — Soit un langage. Les conditions suivantes sont équivalentes :
- est rationnel ;
- Il existe un entier tel que vérifie la condition ;
- Il existe un entier tel que vérifie la condition .
Elle est cependant « non-locale » puisque pour chaque mot, il faut trouver une factorisation qui marche uniformément par rapport à tous les quotients à droite de ce mot.
Théorème d'Ehrenfeucht, Parikh et Rozenberg
[modifier | modifier le code]Un théorème prouvé par Andrzej Ehrenfeucht, Rohit Jivanlal Parikh et Grzegorz Rozenberg[5] donne une condition, fondée sur un renforcement du lemme de l'étoile par blocs, qui est nécessaire et suffisante pour qu'un langage soit rationnel et qui est « locale » au sens précédent.
On dit qu'un langage sur l'alphabet vérifie la condition pour un entier si pour tout mot , et pour toute factorisation , où les mots sont non vides, il existe deux indices avec tels que
- pour tout .
L'équivalence équivaut à la conjonction des deux implications :
- et
- .
On dit que vérifie la condition si pour tout mot , et pour toute factorisation , où les mots sont non vides, il existe deux indices avec tels que
- .
Théorème d'Ehrenfeucht, Parikh et Rozenberg — Soit un langage. Les conditions suivantes sont équivalentes :
- est rationnel ;
- il existe un entier tel que vérifie la condition ;
- il existe un entier tel que vérifie la condition .
Il convient de noter une différence importante avec le théorème de Jaffe énoncée précédemment. Les conditions et portent sur une factorisation d'un mot et de tous ses quotients à droite tandis que les conditions et portent sur toutes les factorisations possibles d'un seul mot, ce qui assure leur caractère local.
L'implication difficile est . Elle utilise, à la place du principe des tiroirs, le théorème de Ramsey.
Notes
[modifier | modifier le code]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, , p. 143-172
- William F. Ogden, « A Helpful Result for Proving Inherent Ambiguity », Mathematical Systems Theory, vol. 2, no 3, , p. 191-194 (DOI 10.1007/BF01694004)
- Jeffrey Jaffe, « A Necessary and Sufficient Pumping Lemma for Regular Languages », SIGACT News, vol. 10, no 2, , p. 48–49 (ISSN 0163-5700, DOI 10.1145/990524.990528, lire en ligne)
- Andrzej Ehrenfeucht, Rohit Jivanlal Parikh et Grzegorz Rozenberg, « Pumping lemmas for regular sets », SIAM J. Comput., vol. 10, , p. 536–541
- Olivier Carton, Langages formels, calculabilité et complexité, [détail de l’édition] (lire en ligne)
- Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, , 816 p. (ISBN 978-2-7117-4807-5)Traduction anglaise avec corrections : Elements of Automata Theory, Cambridge University Press 2009, (ISBN 978-0-52184425-3)
Voir aussi
[modifier | modifier le code]- Expression rationnelle
- Théorème de Kleene
- Lemme d'itération
- Lemme d'itération pour les langages algébriques
- Lemme d'Ogden