Lemme de l'étoile
En théorie des langages, le lemme de l'étoile ou lemme d'itérationModèle:Référence nécessaire pour les langages rationnels (ou encore lemme de gonflementModèle:Référence nécessaire, lemme de pompageModèle:Référence nécessaire, lemme de la pompeModèle:Référence nécessaire, Modèle:Langue 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 suffisammentModèle: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<ref>Modèle:Harvsp</ref>. 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
Considérons le langage des mots qui commencent par un certain nombre de <math>a</math>, suivi par le même nombre de <math>b</math>. 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
Dans l'énoncé suivant <math>|w|\,</math> dénote la longueur du mot <math>w</math>. On écrit <math>y^n</math>pour dire que l'on <math>n</math> copies du mot <math>y</math>. Pour n = 0, <math>y^n</math> est le mot vide.Modèle:Théorème
Dans l'énoncé, l'entier <math>N</math> ne dépend que de <math>L</math> et non pas du mot <math>w</math> choisi. Il est parfois appelé constante d'itérationModèle:Référence nécessaire. Le facteur central <math>y</math> de la factorisation <math>w=xyz</math> est appelé un facteur itérantModèle:Référence 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 :
- <math>xy^*z \subseteq L</math>.
Parmi les itérés <math>xy^nz</math> qui sont dans le langage figure aussi le mot <math>xz</math> obtenu pour <math>n=0</math>.
Il existe de nombreuses variantes de ce lemme ; la plus fréquente stipule, au lieu de la condition <math>|y|\le N</math>, la condition <math>|xy|\le N</math>, et donc que le facteur itérant <math>y</math> se situe près du début du mot.
Exemples d'application du lemme de l'étoile
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
Montrons par exemple que le langage <math> L = \{a^n b^n \mid n\ge0\}</math> sur l'alphabet <math>A= \{a,b\}</math> n'est pas rationnel. Il s'agit du langage qui des mots qui commencent par un certain nombre de <math>a</math>, suivi par le même nombre de <math>b</math>. Il contient le mot vide, <math>ab</math>, <math>aabb</math>, <math>aaabbb</math>, etc. Supposons par l'absurde que <math>L</math> est rationnel. Dans ce cas, on peut appliquer le lemme de l'étoile. Soit <math>N</math> une constante d'itération de <math>L</math>. Considérons le mot <math>w = a^N b^N</math>. Par le lemme, il existe un mot <math>w=xyz</math> vérifiant les conditions du lemme de l'étoile. En particulier, et en utilisant la variante énoncée, on a <math>|xy| \le N </math>, et donc <math>x</math> et <math>y</math> sont composés uniquement de lettres <math>a</math>. Posons <math>k=|y|\,</math>. On a <math>k>0</math> et <math>y = a^k</math>. Alors <math> xy^nz = a^{N+(n-1)k}b^N </math> pour tout entier <math>n\ge0</math>. Comme ces mots devraient être dans <math>L</math> on devrait avoir <math> {N+(n-1)k}=N </math> pour tout entier <math>n\ge0</math> et donc <math>k=|y|=0\,</math>, ce qui est en contradiction avec l'hypothèse. Donc <math>L</math> n'est pas rationnel.
D'autres cas d'applications
On montre de même que
- le langage des palindromes sur <math>A = \{a,b\}</math> n'est pas rationnelModèle:Référence nécessaire,
- le langage <math>\{ w \in X^* : |w|_a = |w|_b \}</math> sur <math>A = \{a,b\}</math> (où <math> |w|_a\, </math> désigne le nombre d'occurrences de la lettre <math>a</math> dans le mot <math>w</math>) est composé des mots qui ont autant de <math>a</math> que de <math>b</math>. Il n'est pas rationnelModèle:Référence nécessaire.
Un peu plus compliqué est la preuve que le langage <math>\{ a^nb^m\mid 0\le n\le m\}</math> n'est pas rationnelModèle:Référence nécessaire. De même, le langage <math>\{ a^nb^m\mid n\ne m\}</math> n'est pas rationnelModèle:Référence nécessaire. Au lieu de faire une preuve directe, il vaut mieux passer par le langage complément.
Preuve du lemme de l'étoile
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 <math>L</math> un langage rationnel, sur un alphabet <math>A</math>. Par le théorème de Kleene, il existe un automate fini <math>\mathcal{A}</math> qui reconnaît <math>L</math>. Soit <math>N</math> le nombre d'états de cet automate. Soit <math>w</math> un mot de <math>L</math> de longueur <math>|w|\ge N\,</math>. Comme <math>w</math> est dans <math>L</math>, il est reconnu par <math>\mathcal{A}</math>, et il existe un chemin acceptant <math> q_0 \xrightarrow{w}t </math> de l'état initial noté ici <math>q_0</math> vers un état terminal <math>t</math> d'étiquette <math>w</math>. Soient <math>a_1,a_2,\ldots,a_N</math> les <math>N</math> premières lettres de <math>w</math>, posons <math> w=a_1a_2\cdots a_Nw'</math>, et soient <math>q_1,q_2,\ldots,q_N</math> les états successifs atteints après la lecture de ces lettres. On a alors le chemin suivant :
- <math>q_0\xrightarrow{a_1}q_1\xrightarrow{a_2}q_2\cdots q_{N-1}\xrightarrow{a_N}q_N\xrightarrow{w'}t.</math>
Le principe des tiroirs dit que, parmi les <math>N+1</math> états <math>q_0,q_1,\ldots,q_N</math>, deux d'entre eux sont égaux. Il existe donc deux entiers <math>k,\ell</math> avec <math>0\le k<\ell\le N</math> tels que <math>q_k=q_\ell</math>. Posons <math>q=q_k=q_\ell</math> et
- <math>x=a_1a_2\cdots a_k,\ y=a_{k+1}\cdots a_\ell,\ z=a_{\ell+1}\cdots a_Nw'.</math>
Le chemin d'étiquette <math>w</math> se factorise de la façon suivante :
- <math>q_0\xrightarrow{x}q\xrightarrow{y}q\xrightarrow{z}t.</math>
Il en résulte que <math>q\xrightarrow{y^n}q</math> pour tout entier <math>n\ge0</math>, et donc que <math>xy^nz</math> est dans <math>L</math> pour tout entier <math>n\ge0</math>. Enfin, on a <math>|y|=\ell-k</math>, donc <math>0<|y|\le N</math>. Ceci prouve le lemme.
La preuve montre en fait la variante du lemme énoncée ci-dessus, à savoir que de plus, on a <math>|xy|\le N</math>, puisque <math>|xy|=\ell</math>.
Le lemme est une condition nécessaire mais non suffisante de rationalité
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 <math>u^R </math> l'image miroir d'un mot <math>u</math>, et soit <math> L = \{ uu^Rv\mid\ u,v \in \{a,b\}^+\}</math> l'ensemble des mots qui ont un préfixe qui est un palindrome non vide de longueur paire.
Posons <math> N=4 </math>, et soit <math> w = uu^Rv </math> un mot de longueur au moins 4 du langage. Si <math>u</math> est une lettre, la factorisation <math>w=xyz</math> avec <math>x=uu^R</math>, <math>y</math> la première lettre de <math>v</math> et <math>z</math> le reste du mot convient. Si <math>u</math> est de longueur au moins 2, on choisit pour <math>x</math> le mot vide, pour <math>y</math> la première lettre de <math>u</math>, et pour <math>z</math> le <math>u</math> reste du mot. Pour <math> N\ge2</math>, le mot <math>xy^Nz</math> commence par le palindrome non vide <math>yy</math>; pour <math> N=0</math>, le mot <math>xy^Nz=z</math> commence par le palindrome formé de <math>u</math> privé de sa première lettre, suivi de l'image miroir de ce suffixe (lui-même suivi de la première lettre de <math>u</math>).
- Un autre exemple
Le langage <math>L = \left\{a^mb^nc^n \mid m,n \ge 1\right\} \cup \{b^mc^n \mid m,n \ge 0 \}</math> n'est pas rationnel mais vérifie les conditions du lemme de l’étoile ; en effet, tout mot <math>z \in L</math> se factorise en <math>z = uvw</math>, de manière que <math>uv^iw \in L</math> pour <math>i\ge0</math>. Pour cela, on choisit pour <math>v</math> la première lettre : c'est soit la lettre <math>a</math>, et le nombre de <math>a</math> est arbitraire, ou c'est un <math>b</math> ou <math>c</math> sans <math>a</math> e tête, et le nombre de <math>b</math> ou <math>c</math> est arbitraire.
Extensions
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
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é :
Exemple d'utilisation du choix du facteur itérant
Sur l'alphabet <math>\{a,b\}</math>, en posant, pour tout mot <math>u</math> sur cet alphabet: <math>|u|_a</math> et <math>|u|_b</math>, respectivement le nombre de <math>a</math> et le nombre de <math>b</math> dans <math>u </math>, on a que l'ensemble des mots <math>u </math> tels que <math>|u|_a=|u|_b</math> vérifie la conclusion du lemme de l'étoile (en prenant <math>N=2</math>, il existe, dans tous mots de cet ensemble, un <math>a</math> et un <math>b</math> 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 <math>vabv'</math> (le cas <math>vbav'</math> étant similaire), on a que, pour tout entier naturel n, <math>v(ab)^nv'</math> 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 <math>N</math>. On pose alors: <math>w=a^Nb^N</math> et <math>u=a^N</math>, <math>w'=b^N</math> et <math>v</math>, le mot vide. On dispose alors d'une factorisation de la forme: <math>w'=xyz</math> respectant la conclusion du choix du facteur itérant. Or: <math>|uxy^2zv|_b>|uxyzv|_b</math> et <math>|uxy^2zv|_a=|uxyzv|_a</math>, ce qui est absurde.
Preuve du lemme avec choix du facteur itérant
Le schéma de la preuve est semblable à celui du premier lemme de l'étoile énoncé. Soit <math>L</math> un langage rationnel, sur un alphabet <math>A</math>, soit <math>\mathcal{A}</math>, un automate fini reconnaissant <math>L</math> et soit <math>N</math> son nombre d'états. Soit <math>w</math> un mot de <math>L</math>, et soit <math>uw'v</math>, une factorisation de ce mot telle que <math>|w'|\ge N</math>. On pose <math>w'=a_1\cdots a_Ns</math> où les <math>a_i</math> sont des lettres et où <math>s</math> le suffixe de <math>w'</math> la longueur <math>|w'|-N</math>. Il existe une suite <math>i, q_0,q_1,\ldots,q_N,q',t</math> d'états, où <math>i</math> est initial et <math>t</math> est terminal, tels que
- <math>i\stackrel{u}\longrightarrow q_0</math>, <math>q_0\stackrel{a_1}\longrightarrow q_1\stackrel{a_2}\longrightarrow q_2\cdots q_{N-1}\stackrel{a_N} \longrightarrow q_N</math> et <math>q_N\stackrel{s}\longrightarrow q'\stackrel{v}\longrightarrow t</math>.
Par le principe des tiroirs, il existe deux entiers <math>0\le k <\ell\le N</math> tels que <math>q_k=q_{\ell}</math>. Posons
- <math>q=q_k=q_{\ell}</math>, <math>x=a_1\cdots a_k, y= a_{k+1}\cdots a_\ell</math>, <math>z=a_{\ell+1}\cdots a_Ns</math>.
Alors
- <math>q_0\stackrel{x}\longrightarrow q \stackrel{y}\longrightarrow q \stackrel{z}\longrightarrow q'</math> et de plus <math>q \stackrel{y^n}\longrightarrow q</math>
pour tout entier naturel <math>n</math>. L'automate reconnaît donc tous les mots de la forme <math>uxy^nzv</math>, et de plus <math>0<|y|=\ell-k-1\le N</math>.
Lemme de l'étoile par blocs
Dans cette variante, on découpe le mot en blocs, et c'est un groupe de blocs que l'on peut itérer:
Modèle:Théorème Dans cet énoncé et les suivants, on convient que <math>w_1w_2\cdots w_k</math> est égal au mot vide si <math>k=0</math>, et de même <math>w_{\ell+1}\cdots w_N</math> est égal au mot vide si <math>\ell=N</math>.
Preuve du lemme de l'étoile par blocs
Soit <math>L</math> un langage rationnel. Par théorème de Kleene, il existe un automate fini <math>\mathcal{A}</math> reconnaissant <math>L</math>. Soit <math>N</math> le nombre d'états de <math>\mathcal{A}</math> et soit <math>w=uw_1\cdots w_Nv</math> un mot de <math>L</math> Il existe une suite d'états <math>i,q_0,q_1,\ldots,q_N,t</math> tels que
- <math>i\stackrel{u}\longrightarrow q_0\stackrel{w_1}\longrightarrow q_1\ \cdots\ q_{N-1} \stackrel{w_N}\longrightarrow q_{N}\stackrel{v}\longrightarrow t</math>,
où <math>i</math> est initial et <math>t</math> est terminal. Par le principe des tiroirs, il existe deux indice <math>0\le k<\ell \le N</math> tels que <math>q_k=q_\ell</math>. On a donc, en notant <math>q</math> cet état et <math>z=w_{k+1}\cdots w_\ell</math>, que
- <math>q\stackrel{z}\longrightarrow q</math>
dans l'automate. On en déduit le résultat souhaité : pour tout entier naturel <math>n</math>, le mot<math>w=uw_1\cdots w_kz^nw_{\ell+1}\cdots w_Nv</math> est un mot accepté par l'automate et est donc un mot de <math>L</math>.
Contre-exemple à la réciproque du lemme de l'étoile par blocs
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 <math>A=\{a,b,c\}</math> et <math>B=\{a,b,c,\#\}</math> ; soit <math>K = \{ uu\mid\ u \in \ A^+\}</math> et <math>K' = \{ u\#v \mid\ u,v \in \ A^* \text{ et } u \neq v\}</math>. Le langage <math>L</math> défini par:
- <math>L=K'\cup A^*KA^*\#A^*\cup A^*\#A^*KA^*</math>
vérifie la conclusion du lemme de l'étoile par blocs. Cependant, il n'est pas rationnel<ref>Modèle:Harvsp. </ref>.
Lemme de l'étoile à la Ogden
Le lemme d'Ogden<ref>Modèle:Harvsp</ref>, initialement conçu pour les langages algébriques, s'applique aussi bien aux langages rationnels. Étant donné un mot <math>w=a_1a_2\cdots a_n</math>, où les <math>a_i</math> sont des lettres, on appelle position dans <math>w</math> tout entier de l'ensemble <math>\{1,2,\ldots,n\}</math>. Un choix de <math>N</math> positions distinguées dans <math>w</math> (ceci est la terminologie habituelle, un peu alambiquée) est simplement un sous-ensemble <math>I\subset\{1,2,\ldots,n\}</math> de positions contenant <math>N</math> éléments. Avec ces définitions, le lemme s'énonce comme suit:
Si l'on distingue toutes les positions dans <math>w</math>, on retrouve le lemme de l'étoile initial. Si l'on considère la factorisation de <math>w</math> 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
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
Une première caractérisation, qui se fonde sur un renforcement du lemme de l'étoile « faible » est celle de J. Jaffe<ref>Modèle:Harvsp</ref>.
On dit qu'un langage <math>L</math> satisfait la condition <math>(J_N)</math> pour un certain entier naturel <math>N</math> si pour tout mot <math>w</math> de longueur <math>N</math>, il existe une factorisation <math>w=uvz</math> avec <math>v</math> non vide telle que: <math>\forall t \in A^*, \forall n \in \mathbb{N}, wt \in L \iff uv^nzt \in L</math>
On dit qu'un langage <math>L</math> satisfait la condition <math>(J'_N)</math> pour un certain entier naturel <math>N</math> si pour tout mot <math>w</math> de longueur <math>N</math>, il existe une factorisation <math>w=uvz</math> avec <math>v</math> non vide telle que: <math>\forall t \in A^*, wt \in L \iff uzt \in L</math>
On a alors le théorème de Jaffe:
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
Un théorème prouvé par Andrzej Ehrenfeucht, Rohit Jivanlal Parikh et Grzegorz Rozenberg<ref>Modèle:Harvsp</ref> 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 <math>L</math> sur l'alphabet <math>A</math> vérifie la condition <math>(E_N)</math> pour un entier <math>N</math> si pour tout mot <math>w</math>, et pour toute factorisation <math>w=w=uw_1w_2\cdots w_Nv</math>, où les mots <math>w_i</math> sont non vides, il existe deux indices <math>k,\ell</math> avec <math> 0\le k<\ell\le N</math> tels que
- <math>w\in L \iff uw_1w_2\cdots w_k(w_{k+1}\cdots w_\ell)^nw_{\ell+1}\cdots w_Nv\in L</math> pour tout <math>n \in \N</math>.
L'équivalence équivaut à la conjonction des deux implications :
- <math>w\in L \implies uw_1w_2\cdots w_k(w_{k+1}\cdots w_\ell)^*w_{\ell+1}\cdots w_Nv\subset L</math> et
- <math>w\in A^*\setminus L \implies uw_1w_2\cdots w_k(w_{k+1}\cdots w_\ell)^*w_{\ell+1}\cdots w_Nv\subset A^*\setminus L</math>.
On dit que <math>L</math> vérifie la condition <math>(E'_N)</math> si pour tout mot <math>w</math>, et pour toute factorisation <math>w=w=uw_1w_2\cdots w_Nv</math>, où les mots <math>w_i</math> sont non vides, il existe deux indices <math>k,\ell</math> avec <math> 0\le k<\ell\le N</math> tels que
- <math>w\in L \iff uw_1w_2\cdots w_kw_{\ell+1}\cdots w_Nv\in L</math>.
Il convient de noter une différence importante avec le théorème de Jaffe énoncée précédemment. Les conditions <math>(J_N)</math> et <math>(J'_N)</math> portent sur une factorisation d'un mot et de tous ses quotients à droite tandis que les conditions <math>(E_N)</math> et <math>(E'_N)</math> portent sur toutes les factorisations possibles d'un seul mot, ce qui assure leur caractère local.
L'implication difficile est <math>(3)\implies(1)</math>. Elle utilise, à la place du principe des tiroirs, le théorème de Ramsey.
Modèle:Démonstration/début On s'inspire ici de l'exposition donnée dans les livres de Carton et de Sakarovitch<ref>Modèle:Harvsp</ref>. On procède en trois étapes:
- a) On montre que si <math>L</math> vérifie la condition <math>(E'_N)</math> pour un certain entier naturel <math>N</math> alors ses quotients à gauche aussi.
- b) On montre, grâce au théorème de Ramsey, que pour tout entier naturel <math>N</math>, le nombre de langages vérifiant la condition <math>(E'_N)</math> est fini.
- c) On utilise le théorème de Myhill-Nerode pour conclure : le langage <math>L</math>, ayant un nombre fini de quotients à gauche, est reconnaissable par un automate fini, donc rationnel d'après le théorème de Kleene.
Preuve du point a): Soient <math>N \in \mathbb{N}</math> et <math>L</math> vérifiant la condition <math>(E'_N)</math>. Soit <math>f</math> un mot. Soient <math>w</math> un mot et soit <math>w=w=uw_1w_2\cdots w_Nv</math> une factorisation, où les mots <math>w_i</math> sont non vides. Grâce à la condition <math>(E'_N)</math>, on sait qu'il existe deux indices <math>k,\ell</math> avec <math> 0\le k<\ell\le N</math> tels que:
- <math>fw\in L \iff fuw_1w_2\cdots w_kw_{\ell+1}\cdots w_Nv\in L</math>.
On a alors:
- <math>\begin{align}w \in f^{-1}L &\iff fw \in L \iff fuw_1w_2\cdots w_kw_{\ell+1}\cdots w_Nv\in L\\ &\iff uw_1w_2\cdots w_kw_{\ell+1}\cdots w_Nv\in f^{-1}L\end{align}</math>
ce qui montre que <math>f^{-1}L </math> vérifie la condition <math>(E'_N)</math>.
Preuve du point b): On utilise le théorème de Ramsey sous la forme suivante, équivalente à celle énoncée pour les graphes dans l'article théorème de Ramsey. Dans cet énoncé, <math>P_{k}(X)</math> dénote l'ensemble des parties à <math>k</math> éléments d'un ensemble <math>X</math>.
Modèle:Théorème Soient donc <math>N \in \N</math> et <math>R=R(2, 2, N+1)</math>. Montrons que si deux langages <math>L</math> et <math>K</math> vérifiant la condition <math>(E'_N)</math> coïncident sur les mots de longueur <math>\le R</math> alors ils sont égaux. Ceci fournira une injection de l'ensemble des langages vérifiant <math>(E'_N)</math> vers l'ensemble des parties de l'ensemble des mots de longueur <math>\le R</math>, qui est un ensemble fini, ce qui permettra de conclure.
Pour ce faire, on procède par récurrence forte sur la longueur d'un mot. Si <math>w</math> est un mot de longueur <math>\le R</math> alors <math>w \in L \iff w \in K</math> par hypothèse. On suppose maintenant que <math>w</math> est de longueur <math>M > R</math> et que <math>L</math> et <math>K</math> coïncident sur les mots de longueur <math> <M </math>. On factorise <math>w</math> en <math>w = w_0w_2\cdots w_Rv</math> où les <math>w_i</math> sont des lettres et <math>v</math> un mot. On considère l'ensemble <math> E=\{1,\ldots,R\} </math> et la partition <math>\{X,\bar{X}\}</math> de <math>P_{2}(E)</math> où
- <math>X=\{ \{i,j\} \in P_{2}(E) \mid i<j \ \ \text{et} \ \ w_0w_2\cdots w_iw_{j+1} \cdots w_Nv \in L\}</math>
et son complémentaire noté <math>\bar{X}</math>. Par hypothèse de récurrence, on a aussi
- <math>X=\{ \{i,j\} \in P_{2}(E) \mid i<j \ \ \text{et} \ \ w_0w_2\cdots w_iw_{j+1} \cdots w_Nv \in K\}</math>.
Par le théorème de Ramsey, on obtient l'existence d'un sous-ensemble <math> F=\{i_1 < \cdots < i_N\} </math> de <math>E</math> tel que <math>P_{2}(F) \subset X </math> ou <math>P_{2}(F) \subset \bar{X} </math>. On obtient alors une nouvelle factorisation <math>w=uv_1\cdots v_Nz</math> avec
- <math>u=w_0\cdots w_{i_{0}-1}</math> , <math>v_j=w_{i_{j-1}}w_{i_{j-1}+1}\cdots w_{i_{j}-1}</math> pour <math>j=1,\ldots,N</math> et <math>z=w_{i_{N}}\cdots v </math>.
Puisque <math>L</math> et <math>K</math> vérifient la condition <math>(E'_N)</math>, cette factorisation donne deux paires <math> (m,n) \in 0,N^{2} </math> et <math> (m',n') \in 0,N^{2} </math> respectivement qui délimitent des blocs qu'on peut éliminer dans <math>w</math>. Plus précisément :
- <math>\begin{align} w \in L &\iff w_0\cdots w_{i_{m}}w_{i_n+1}\cdots w_Nv \in L \\ &\iff w_0\cdots w_{i_{m'}}w_{i_n'+1}\cdots w_Nv \in L\\ & \iff w_0\cdots w_{i_{m'}}w_{i_n'+1}\cdots w_Nv \in K \iff w \in K\end{align} </math>
par définition de <math>(m,n)</math>, <math>F</math> et <math>(m',n') </math> successivement. Ceci fournit l'hérédité de la propriété et permet de conclure la récurrence. On obtient finalement que si les langages <math>L</math> et <math>K</math> coïncident sur les mots de longueur <math> <R </math>, ils sont égaux, ce qui achève la preuve du point b). Modèle:Démonstration/fin
