Lemme d'Ogden

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 pour les langages algébriques, aussi connu sous le nom de lemme de Bar-Hillel, Perles et Shamir.

Sommaire

Énoncé

Étant donné un mot w=a_1a_2\cdots a_n, où les ai sont des lettres, on appelle position dans w tout entier de l'ensemble \{1,2,\ldots,n\}. Un choix de N positions distinguées dans w (ceci est la terminologie habituelle, un peu alambiquée) est simplement un sous-ensemble I\subset\{1,2,\ldots,n\} de positions contenant N éléments. Avec ces définitions, le lemme s'énonce comme suit:

Lemme d'Ogden — Soit L un langage algébrique. Il existe un entier N tel que pour tout mot w de L de longueur |w|\ge N, et pour tout choix de N positions distinguées dans w, il existe une factorisation w = xuyvz telle que

  1. (x et u et y) ou (y et v et z) contiennent au moins une position position distinguée
  2. uyv contient plus N positions distinguées
  3. xu^nyv^nz \in L pour tout n\ge0.

L'entier N (plus précisément le plus petit entier pour lequel l'éononcé est vrai) est la constante d'Ogden.

Il existe une variante grammaticale du lemme d'Ogden: 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'Ogden (variante grammaticale) — Soit G une grammaire algébrique d'axiome S. Il existe un entier N tel que pour tout mot w qui dérive de S de longueur |w|\ge N, et pour tout choix de N positions distinguées dans w, il existe une factorisation w = xuyvz telle que

  1. (x et u et y) ou (y et v et z) contiennent au moins une position position distinguée
  2. uyv contient plus N positions distinguées
  3. 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.

Exemples d'application

  • Le langage L=\{a^n b^n c^n \mid n \geqslant 0\} n'est pas algébrique. On distingue, dans le mot aNbNcN les lettres égales à a. En applicant le lemme, on fait donc varier le nombre de a. Il faut distinguer encore le cas où le facteur v est vide ou non, mais comme on itère ce fateur, il ne peut être formé que d'un type de lettres, d'où la contradiction.
  • Le langage L=\{a^mb^nc^md^n\mid n,m\ge0\} n’est pas algébrique. On applique la variante du lemme au mot w = aNbNcNdN, où N est la constante d'Ogden, et où les lettres distinguées sont les lettres b. Il existe des dérivations
         S\xrightarrow* a^Nb^kXd^\ell , X\xrightarrow* b^iXd^i, X\xrightarrow* b^{k'}c^Nd^{\ell'}
    avec N=k+i+k'=\ell+i+\ell'. On applique le lemme une deuxième fois, au mot a^Nb^kXd^\ell, où cette fois-ci ce sont les lettres a qui sont distinguées. On obtient une paire itérante contenant de lettres a itérées, mais aucune lettre d, contradiction.
  • Le langage L=\{a^nb^nc^m\mid n,m\ge0\}\cup \{a^mb^nc^n\mid n,m\ge0\} est inhéremment ambigu. Un langage est inhéremment ambigu si toutes les grammaires qui l'engendrent sont ambiguës. On applique une première fois la variante du lemme au mot
        w = aNbNcN + N!,
    où N est la constante d'Ogden, et en distinguant les lettres b. Il existe une dérivation
         S\xrightarrow* xXz\xrightarrow* xuXvz\xrightarrow* xuyvz.
    et les conditions impliquent que u = ai et v = bi pour un entier 0\le i\le N. En itérant N! / i fois la dérivation
         X\xrightarrow* uXv,
    on obtient un arbre de dérivation pour le mot aN + N!bN + N!cN + N!. Cet arbre contient un sous-arbre dont la frontière ne contient que des lettres a et b, dont au moins N! − N lettres b. En appliquant le même procédé au mot
        w = aN + N!bNcN,
    on obtient un autre arbre de dérivation pour le même mot aN + N!bN + N!cN + N!. Cet arbre contient un sous-arbre dont la frontière ne contient que des lettres b et c, dont au moins N! − N lettres b. Cet arbre est donc différent du premier arbre.


Références

  • William F. Ogden, « A Helpful Result for Proving Inherent Ambiguity », dans Mathematical Systems Theory, vol. 2, no 3, 1968, p. 191-194 [lien DOI] 

Voir aussi


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Lemme d'Ogden de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • 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. Énoncé Forme simplifiée Soit L un langage algébrique. Il existe un… …   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'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 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

  • 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

  • Grammaire non contextuelle — En linguistique et en informatique, une grammaire non contextuelle, grammaire hors contexte ou grammaire algébrique (type 2 dans la hiérarchie de Chomsky) est une grammaire formelle dans laquelle chaque règle de production (ou simplement… …   Wikipédia en Français

  • 2002 in film —             List of years in film       (table) … 1992 .  1993 .  1994 .  1995  . 1996  . 1997  . 1998 … 1999 2000 2001 2002 2003 2004 2005 …  …   Wikipedia

Share the article and excerpts

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