Lemme d'Ogden

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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.

Énoncé[modifier | modifier le code]

Étant donné un mot , où les sont des lettres, on appelle position dans tout entier de l'ensemble . Un choix de positions distinguées dans (ceci est la terminologie habituelle, un peu alambiquée) est simplement un sous-ensemble de positions contenant éléments. Avec ces définitions, le lemme s'énonce comme suit:

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

  1. ( et et ) ou ( et et ) contiennent au moins une position distinguée
  2. contient au plus positions distinguées
  3. pour tout .

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

Il existe une variante grammaticale du lemme d'Ogden: elle dit que la paire itérante peut être choisie grammaticale. Cette variante est bien utile dans certains cas. Voici l'énoncé:

Lemme d'Ogden (variante grammaticale) — Soit une grammaire algébrique d'axiome . Il existe un entier tel que pour tout mot qui dérive de de longueur , et pour tout choix de positions distinguées dans , il existe une factorisation telle que

  1. ( et et ) ou ( et et ) contiennent au moins une position distinguée
  2. contient au plus positions distinguées
  3. il existe une variable telle que .

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

Exemples d'application[modifier | modifier le code]

  • Le langage n'est pas algébrique. On distingue, dans le mot les lettres égales à . En appliquant le lemme, on fait donc varier le nombre de . Il faut distinguer encore le cas où le facteur est vide ou non, mais comme on itère ce facteur, il ne peut être formé que d'un type de lettres, d'où la contradiction.


  • Le langage n’est pas algébrique. On applique la variante du lemme au mot , où est la constante d'Ogden, et où les lettres distinguées sont les lettres . Il existe des dérivations
         
    avec . On applique le lemme une deuxième fois, au mot , où cette fois-ci ce sont les lettres qui sont distinguées. On obtient une paire itérante contenant de lettres itérées, mais aucune lettre , contradiction.


  • Le langage 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
        ,
    est la constante d'Ogden, et en distinguant les lettres . Il existe une dérivation
         .
    et les conditions impliquent que et pour un entier . En itérant fois la dérivation
         ,
    on obtient un arbre de dérivation pour le mot . Cet arbre contient un sous-arbre dont la frontière ne contient que des lettres et , dont au moins lettres . En appliquant le même procédé au mot
        ,
    on obtient un autre arbre de dérivation pour le même mot . Cet arbre contient un sous-arbre dont la frontière ne contient que des lettres et , dont au moins lettres . Cet arbre est donc différent du premier arbre.

Références[modifier | modifier le code]

  • William F. Ogden, « A Helpful Result for Proving Inherent Ambiguity », Mathematical Systems Theory, vol. 2, no 3,‎ , p. 191-194 (DOI 10.1007/BF01694004)

Voir aussi[modifier | modifier le code]