Metraipolis › archive › dc_844d368af4bd
Lemme de l'étoile — Wikipedia (fr)
- Source
- Wikipedia (fr)
- Original
- https://fr.wikipedia.org/wiki/Lemme_de_l%27%C3%A9toile
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-11-10T03:39:09.816Z
- SHA-256 of the archived text
677c0566258a2b1c659a39da1d799dbb0a1d8a9ce2b8715ec0cbbaaef45287e1- Stable URL of this page
https://metraipolis.com/documento/dc_844d368af4bd
How to cite
Lemme de l'étoile — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Lemme_de_l%27%C3%A9toile (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_844d368af4bd (Metraipolis archive dc_844d368af4bd, sha256 677c0566258a2b1c659a39da1d799dbb0a1d8a9ce2b8715ec0cbbaaef45287e1)
BibTeX
@misc{dc844d368af4bd,
title = {Lemme de l'étoile — Wikipedia (fr)},
howpublished = {Wikipedia (fr)},
url = {https://fr.wikipedia.org/wiki/Lemme_de_l%27%C3%A9toile},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_844d368af4bd; sha256 677c0566258a2b1c659a39da1d799dbb0a1d8a9ce2b8715ec0cbbaaef45287e1},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Lemme_de_l%27%C3%A9toile. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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'un facteur 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 le facteur est situé 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. 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é. Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in francese, in ordine alfabetico). Fonte: Wikipedia in francese, voce «Lemme de l'étoile» — https://fr.wikipedia.org/wiki/Lemme_de_l%27%C3%A9toile Wikidata Q2292874: «type of pumping lemma» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q2292874 Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Lemme_de_l%27%C3%A9toile?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 225909298, consultata il 2026-11-10T03:35:51.249Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: e6d70bb0d94fd169a729a82ed8b3f7125d16d530ca41ba176c4b18fe2b727579