Metraipolis › archive › dc_2e490f7c71c7

Pumping lemma — Wikipedia

Source
Wikipedia (it)
Original
https://it.wikipedia.org/wiki/Pumping_lemma
License (as archived)
CC-BY-SA-4.0
Archived
2026-11-08T18:51:22.725Z
SHA-256 of the archived text
ecf1df7ff17457b9576f385a2b179c8159df87744097d4e71856b6a347f79fb5
Stable URL of this page
https://metraipolis.com/documento/dc_2e490f7c71c7

How to cite

Pumping lemma — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/Pumping_lemma (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_2e490f7c71c7 (Metraipolis archive dc_2e490f7c71c7, sha256 ecf1df7ff17457b9576f385a2b179c8159df87744097d4e71856b6a347f79fb5)
BibTeX
@misc{dc2e490f7c71c7,
  title = {Pumping lemma — Wikipedia},
  howpublished = {Wikipedia (it)},
  url = {https://it.wikipedia.org/wiki/Pumping_lemma},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_2e490f7c71c7; sha256 ecf1df7ff17457b9576f385a2b179c8159df87744097d4e71856b6a347f79fb5},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/Pumping_lemma. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Il pumping lemma riguarda la presenza in ogni linguaggio context-free infinito (e in particolare in ogni linguaggio regolare infinito) di successioni di stringhe che presentano regolarità ben definite. In particolare ogni stringa sufficientemente lunga di un tale linguaggio contiene una o più porzioni che possono essere ripetute un numero arbitrario di volte ottenendo ancora una stringa appartenente al linguaggio. Il pumping lemma fornisce una condizione necessaria ma non sufficiente affinché un linguaggio sia regolare o context-free, quindi può essere utilizzato per determinare che un particolare linguaggio non sia in una di queste classi, verificando che il linguaggio non soddisfi la condizione necessaria fornita dal pumping lemma.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in italiano, in ordine alfabetico).
Fonte: Wikipedia in italiano, voce «Pumping lemma» — https://it.wikipedia.org/wiki/Pumping_lemma
Wikidata Q1059648 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1059648
Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/Pumping_lemma?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 131645392, consultata il 2026-11-08T18:47:29.720Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 87f549019924c9dc4b3a28b9987adbbae75f7791bc7b8dc60137e462dc095d86