Lemme d'itération pour les langages algébriques

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 est le lemme de l'étoile.

Une version plus élaborée du lemme d'itération est le Lemme d'Ogden.

Sommaire

Énoncé formel

Lemme d'itération — Soit L un langage algébrique. Il existe un entier N tel que tout mot w de L de longueur |w|\ge N possède une factorisation w = xuyvz telle que

  1. 0<|uv|, |uyv|\le N et
  2. xu^nyv^nz \in L pour tout entier n\ge0.

Le lemme indique donc que, dans un langage algébrique, certains facteurs de mots assez longs peuvent être itérés de concert. L'entier N est l'« entier d'itération », le couple (u,v) ou la factorisation (x,u,y,v,z) est une « paire itérante ».

Il existe une variante grammaticale du lemme d'itération: elle dit que la paire itérante (x,u,y,v,z) peut être choisie grammaticale. Cette variante est bien utile dans certains cas. Voici l'énoncé:

Lemme d'itération (variante grammaticale) — Soit G une grammaire algébrique d'axiome S. Il existe un entier N tel que tout mot w qui dérive de S de longueur |w|\ge N possède une factorisation w = xuyvz telle que

  1. 0<|uv|, |uyv|\le N et
  2. il existe une variable X telle que S\xrightarrow* xXz, X\xrightarrow* uXv, X\xrightarrow* y.

Dans cet énoncé, le mot w peut contenir des variables de la grammaire: il appartient au langage « élargi » de tous les mots dérivant de S, qu'ils contiennent ou non des variables.

Exemple d'utilisation du lemme

Prouvons que le langage L = {anbncn | n > 0} n'est pas algébrique. Supposons le contraire, et soit N la constante d'itération du langage. Considérons le mot w = aNbNcN. Il existe une factorisation w = xuyvz vérifiant les propriétés du lemme. Comme xu^nyv^nz \in L pour tout n, chaque mot unvn contient le même nombre de lettres a,b et c, et ce nombre est non nul. Or ceci est impossible si les lettres a doivent précéder les lettres b et celles-ci les lettres c.

Limitations

Comme pour les langages rationnels, le lemme d'itération pour les langages algébriques est une condition nécessaire mais non suffisante. Parmi les lemmes de même nature le lemme d'Ogden est bien plus puissant.

Références

  • Yehoshua Bar-Hillel, Micha A. Perles et Eli Shamir, « On formal properties of simple phrase structure grammars », dans Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung, vol. 14, 1961, p. 143-172 
  • Olivier Carton, Langages formels, calculabilité et complexité, Vuibert, 2008 (ISBN 978-2-7117-2077-4) 
  • (en) Michael Sipser, Introduction to the Theory of Computation, PWS Publishing, 1997 (ISBN 0-534-94728-X)  Section 1.4: Nonregular Languages, pp. 77–83. Section 2.3: Non-context-free Languages, pp. 115–119.

Voir aussi

Lemme d'itération pour les langages rationnels


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Lemme d'itération pour les langages algébriques de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Lemme d'itération —  Ne pas confondre avec le Théorème 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… …   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

  • Grammaire linéaire — En informatique théorique, et notamment en théorie des langages, on appelle grammaire linéaire une grammaire algébrique dont tous les membres droits de règles contiennent au plus un symbole non terminal. Un langage linéaire est un langage qui est …   Wikipédia en Français

  • Langage algébrique — En théorie des langages formels, un langage algébrique ou langage non contextuel est un langage qui peut être engendré par une grammaire algébrique. De manière équivalente un langage algébrique est un langage reconnu par automate à pile. Les… …   Wikipédia en Français

  • LOGIQUE MATHÉMATIQUE — La logique au sens étroit du terme, c’est à dire la logique formelle par opposition à l’épistémologie ou à la théorie de la connaissance, se propose de donner une théorie de l’inférence formellement valide. Elle considère comme valide toute… …   Encyclopédie Universelle

  • Langage contextuel — En informatique théorique, et spécialement en théorie des langages, un langage contextuel (en anglais context sensitive langauge) est un langage formel engendré par une grammaire contextuelle. C est un langage de type 1 dans la hiérarchie de… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”