Metraipolis › archive › dc_ce5ee34bafdd
Lemme d'Ogden — Wikipedia (fr)
- Source
- Wikipedia (fr)
- Original
- https://fr.wikipedia.org/wiki/Lemme_d%27Ogden
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-11-10T03:37:33.216Z
- SHA-256 of the archived text
fb71cf01841bb62dcdfc967cd2bff8f0a511d82f9aeab190ab655b33b0eb04a4- Stable URL of this page
https://metraipolis.com/documento/dc_ce5ee34bafdd
How to cite
Lemme d'Ogden — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Lemme_d%27Ogden (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_ce5ee34bafdd (Metraipolis archive dc_ce5ee34bafdd, sha256 fb71cf01841bb62dcdfc967cd2bff8f0a511d82f9aeab190ab655b33b0eb04a4)
BibTeX
@misc{dcce5ee34bafdd,
title = {Lemme d'Ogden — Wikipedia (fr)},
howpublished = {Wikipedia (fr)},
url = {https://fr.wikipedia.org/wiki/Lemme_d%27Ogden},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_ce5ee34bafdd; sha256 fb71cf01841bb62dcdfc967cd2bff8f0a511d82f9aeab190ab655b33b0eb04a4},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Lemme_d%27Ogden. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
En informatique théorique, le lemme d'Ogden est un résultat de théorie des langages analogue au lemme de l'étoile. On l'utilise principalement pour démontrer que certains langages ne sont pas algébriques. Il est nommé ainsi d'après William F. Ogden, un informaticien théoricien américain qui l’a publié en 1968. Le lemme d'Ogden est une version plus élaborée du lemme d'itération pour les langages algébriques, aussi connu sous le nom de lemme de Bar-Hillel, Perles et Shamir. Il existe des langages qui satisfont le lemme d'Ogden mais qui ne sont pas algébriques. Ce lemme donne une condition nécessaire pour les langages algébriques, mais pas une condition suffisante. Il est très utile, dans sa version grammaticale, pour prouver que certains langages sont inhéremment ambigus. 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 d'Ogden» — https://fr.wikipedia.org/wiki/Lemme_d%27Ogden Wikidata Q1855893: «generalization of the pumping lemma for context-free languages» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1855893 Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Lemme_d%27Ogden?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 206524445, consultata il 2026-11-10T03:34:27.668Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 93de90571315f54b39c0c7bd26c7c07bc9d1602fc7730ce0bc2e2b7fdcaf3364