Discussion:Lemme de l'étoile

Version pour les langages hors contexte

Il faudrait ajouter une section pour les grammaires hors contexte : le mot se décompose en $u.v.w.x.y$ avec $|v.w.x|\leq n$ ($n$ une constante représentant le plus grand mot générable sans récursivité), $|v.x|\neq \epsilon$ et $\forall i\geq 0,u.v^{i}.w.x^{i}.y\in L$. Tom (d) 11 décembre 2007 à 15:14 (CET)

Modification "un exemple d'utilisation du lemme de l'étoile"

Une confusion est possible entre le "n" énoncé dans la définition du langage rationnel $L=\{a^{n}b^{n}\mid n\geq 0\}$ et celui de la formule venant du lemme (énoncée quelques lignes après): $xy^{n}z=a^{N+(n-1)k}b^{N}$.

De même la formule $xy^{n}z=a^{N+(n-1)k}b^{N}$ n'est pas triviale, préciser par exemple $x=a,y=a^{k},z=a^{N-(k+1)}b^{N}.$

Enfin, ajouter quelque chose comme "égalité des exposants" avant ou après la formule ${N+(n-1)k}=N$

Zehta (d) 26 juillet 2013 à 14:29 (CEST)

Ajouts dans "conditions nécessaires et suffisantes"

J'ai ajouté la partie sur le théorème de Jaffe et la preuve du théorème d'Ehrenfeucht, Parikh, Rozenberg (ci-après nommé théorème EPR). J'ai aussi ajouté les références à l'article de Jaffe et au livre de Sakarovitch. Voici ce que j'ai fait:

1)Pour le théorème de Jaffe, j'ai jugé que c'était un ajout qui permettait de rajouter du contexte (sans mauvais jeu de mot) à la partie sur les conditions nécessaires et suffisantes. J'ai choisi de ne pas mettre la preuve du théorème. On peut la trouver dans l'article original ou dans le livre de Sakarovitch (sous forme d'exercice corrigé). J'ai accès à ces deux références. Si vous souhaitez que ceci soit ajouté (et pourquoi), dites-le moi. La preuve est substantiellement plus courte que celle du théorème EPR.

2)La discussion sur le caractère local des conditions du théorème de Jaffe et du théorème EPR est inspirée de celles présentes dans l'article EPR et dans le livre de Sakarovitch. Je ne sais pas si il faut indiquer précisément ce fait dans l'article ou non, et si oui, indiquer les passages précis. Je ne sais pas non plus si la discussion paraît suffisamment claire à un observateur extérieur (est-il assez explicite que le théorème EPR est en un sens "meilleur" que le théorème de Jaffe, au sens où les conditions du théorème EPR sont, à un mot fixé, "finiment vérifiables"/combinatoires (si j'ai bien compris cela) contrairement à celles du théorème de Jaffe, qui portent un quantificateur universel?).

3)Pour la preuve du théorème EPR, j'ai choisi de suivre les livres de Carton et Sakarovitch plutôt que l'article EPR. Les deux livres suivent à peu près le même schéma, qui est d'ailleurs celui de l'article EPR, mais l'exposition est un peu différente. Par exemple, les notations pour les conditions $(E_{N})$ et $(E'_{N})$ sont échangées de Carton à Sakarovitch. En ce qui concerne le théorème de Ramsey, Sakarovitch cite la version que j'ai indiqué dans l'article, Carton une version "fonctionnelle" qui lui est équivalente.

Voici quelques détails en plus sur la preuve:

Les deux premières implications sont essentiellement considérées comme triviales dans les livres de Carton et de Sakarovitch. Pour $(1)\implies (2)$, Sakarovitch indique quand même qu'en reprenant la preuve du lemme de l'étoile par blocs, on obtient le résultat. Les deux preuves sont par contre traitées intégralement dans l'article EPR. Pour ma part, j'ai écrit deux preuves qui reflètent la façon dont je comprenais ces implications et qui faisaient le lien avec l'exposition déjà donnée dans l'article avant mes modifications. En particulier, la deuxième preuve n'est pas celle de l'article EPR. Si ceci est considérée comme une mauvaise pratique, n'hésitez pas à me le signaler. J'ai accès à l'article EPR et j'essaierai à ce moment de réécrire la preuve pour qu'elle corresponde au mieux à celle de l'article.

Pour la partie la plus difficile, c'est-à-dire celle sur le théorème de Ramsey, j'ai encore une fois exposé les choses de la façon qui était, pour moi, la plus claire. Elle s'inspire donc de l'exposition de Carton ET de celle de Sakarovitch. Par exemple, l'énoncé du théorème de Ramsey est celui qu'on retrouve dans le livre de Sakarovitch tandis que la fin de la preuve correspond beaucoup plus à celle présente dans le livre de Carton. Si ce "manque" de cohérence est une mauvaise pratique, n'hésitez pas à me le signaler. J'essaierais alors de corriger ceci du mieux que je peux. De même, si la preuve n'est pas claire du tout, dites-le moi.

Quelques détails sur le livre de Sakarovitch: La traduction anglaise de Reuben Thomas contient des corrections par rapport à l'édition française. Je ne sais pas exactement quelles modifications ont été faites. On trouve cependant sur le site de Sakarovitch une page dédiée au livre avec une liste d'errata pour l'édition française, et qui date d'avant la publication de l'édition anglaise:http://perso.telecom-paristech.fr/~jsaka/ETA/eta.html

Je trouve aussi qu'il serait peut-être bon de créer un espace référence dédié au livre de Jacques Sakarovitch, comme pour le livre d'Olivier Carton puisque ça fait déjà au moins deux articles où il est cité (Théorème de Kleene et celui-ci). J'avais commencé à faire un brouillon mais je préférais soulever la question avant.

Je suis ouvert à toute remarque, feedback... sur les modifications que j'ai effectuées. --Hadhramaut (discuter) 6 décembre 2016 à 17:27 (CET)

Fusion entre Lemme d'itération et Lemme de l'étoile

Discussion transférée depuis Wikipédia:Pages à fusionner
Les deux pages parlent du pumpimg lemma, la première étant une ébauche relative à une des noms en français du lemme (ce même nom est présent dans lemme de l'étoile aussi). --Ruthven (msg) 1 septembre 2021 à 13:14 (CEST)

Contre La première parle de lemme d'itération = pumping lemma en anglais : elle présente les lemmes d'itération pour les rationnels, les algébriques, etc. C'est une sorte de chapeau. La deuxième parle de lemme d'itération pour les langages rationnels seulement ; pour être plus clair, j'ai complété en ce sens le nom long.

Il en est de même en anglais par exemple.

Lemme de l’étoile = pumping lemma for regular languages

Lemme d’itération = pumping lemma

Un confusion provenait d'une mauvaise liaison entre les correspondances via Wikidata. Une réparation u moins partielle a été faite. -- ManiacParisien (discuter) 2 septembre 2021 à 11:41 (CEST)

---

Pas de consensus, je clôture. Nouill 17 septembre 2021 à 09:20 (CEST)

Rajouter les cas triviaux (automates sans boucle) dans la preuve  ?

Je ne me sens pas assez compétent pour le faire moi-même, mais quand il est écrit dans l'article :

Soit $w$ un mot de $L$ de longueur $|w|\geq N\,$

cela me pose problème car cela suppose qu'il existe forcément un mot de longueur $N$ dans $L$.

Or, si l'automate ne comporte pas de boucle, on a forcément $|w|<N\,$.

La preuve qu'Olivier Carton présente dans Langages formels, Calculabilité et Complexité Année 2007/2008, Formation interuniversitaire en informatique de l'École Normale Supérieur (2008) remplace cette phrase par "Soit $w$ un mot de $L$. Si $|w|\geq N\,$ [...]". — Le message qui précède, non signé, a été déposé par Hl037 (discuter), le 26 janvier 2022 à 13:25 (CET)