Lemme d'itération
- Lemme d'itération
-
En informatique théorique, et spécialement en théorie des langages, un lemme d'itération (pumping lemma en anglais) est un énoncé qui stipule que, dans un langage formel d'une classe particulière, tout mot assez long du langage possède un ou des facteurs qui peuvent être enlevés ou répétés, séparément ou de concert, tout en restant à l'intérieur du langage. Les preuves de ces lemmes utilisent, comme argument de base, le principe des tiroirs.
Les deux exemples le plus importants de lemme d'itération sont le lemme de l'étoile pour les langages rationnels et le lemme d'itération pour les langages algébriques, parfois appelé improprement le lemme de la double étoile.
Le lemme d'Ogden est une version plus forte du lemme d'itération pour les langages algébriques.
Ces lemmes sont utilisés pour prouver qu'un langage particulier n'est pas dans la classe de langage considérée. Ils ne peuvent pas être utilisés pour vérifier qu'un langage est dans la classe donnée, puisque le lemme ne donne qu'une condition nécessaire, mais pas suffisante d'appartenance.
Bibliographie
Voir aussi
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Lemme d'itération de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Lemme d'itération pour les langages algébriques — Le Lemme d itération pour les langages algébriques, aussi connu sous le vocable Lemme de Bar Hillel, Perles et Shamir, donne une condition de répétition nécessaire pour les langages algébriques. Sa version simplifiée pour les langages rationnels… … Wikipédia en Français
Lemme De L'étoile — En théorie des langages, le lemme de l étoile (ou encore lemme d itération, lemme de pompage, pumping lemma en anglais) décrit une propriété essentielle de tout langage rationnel. Informellement, il établit que tout mot suffisamment long d un… … Wikipédia en Français
Lemme de l'etoile — Lemme de l étoile En théorie des langages, le lemme de l étoile (ou encore lemme d itération, lemme de pompage, pumping lemma en anglais) décrit une propriété essentielle de tout langage rationnel. Informellement, il établit que tout mot… … Wikipédia en Français
Lemme de pompage — Lemme de l étoile En théorie des langages, le lemme de l étoile (ou encore lemme d itération, lemme de pompage, pumping lemma en anglais) décrit une propriété essentielle de tout langage rationnel. Informellement, il établit que tout mot… … Wikipédia en Français
Lemme de l'étoile — En théorie des langages, le lemme de l étoile (ou encore lemme d itération, lemme de pompage, lemme de la pompe, pumping lemma en anglais) énonce une propriété typique de tout langage rationnel. Informellement, il stipule que tout mot… … Wikipédia en Français
Lemme d'Ogden — 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. Le lemme d Ogden est une version plus élaborée du lemme d itération… … Wikipédia en Français
Lemme De Grönwall — En mathématiques, le lemme de Grönwall, nommé d après Thomas Hakon Grönwall (1877 1932) qui l établit en 1919, permet l estimation d une fonction qui vérifie une certaine inégalité différentielle. Le lemme existe sous deux formes, intégrale et… … Wikipédia en Français
Lemme de Gronwall — Lemme de Grönwall En mathématiques, le lemme de Grönwall, nommé d après Thomas Hakon Grönwall (1877 1932) qui l établit en 1919, permet l estimation d une fonction qui vérifie une certaine inégalité différentielle. Le lemme existe sous deux… … Wikipédia en Français
Lemme de grönwall — En mathématiques, le lemme de Grönwall, nommé d après Thomas Hakon Grönwall (1877 1932) qui l établit en 1919, permet l estimation d une fonction qui vérifie une certaine inégalité différentielle. Le lemme existe sous deux formes, intégrale et… … Wikipédia en Français
Lemme de Grönwall — En mathématiques, le lemme de Grönwall, nommé d après Thomas Hakon Grönwall (en) qui l établit en 1919, permet l estimation d une fonction qui vérifie une certaine inégalité différentielle. Le lemme existe sous deux formes, intégrale et… … Wikipédia en Français
