En informatique théorique, 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. Il est nommé ainsi d'après William F. Ogden, un informaticien théoricien américain qui l’a publié en 1968[1].

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.

Il existe des langages qui satisfont le lemme d'Ogden mais qui ne sont pas algébriques. Ce lemme donne une condition nécessaire pour les langages algébriques, mais pas une condition suffisante. Il est très utile, dans sa version grammaticale, pour prouver que certains langages sont inhéremment ambigus.

Énoncés

modifier

Lemme d'Ogden

modifier

Étant donné un mot  , où les   sont des lettres, on appelle position dans   tout entier de l'ensemble  . Un choix de   positions distinguées ou positions marquées dans   (ceci est la terminologie traditionnelle) 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  .

Le plus petit entier   pour lequel l'énoncé est vrai est appelé la constante d'Ogden.

Variante grammaticale

modifier

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, et notamment pour les langages inhéremment ambigus. 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 au moins   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 » constitué par définition de tous les mots dérivant de  , qu'ils contiennent ou non des variables.

Exemples d'application

modifier

Langages non algébriques

modifier
  • Le langage   n'est pas algébrique. Pour le voir, on distingue dans le mot   les lettres égales à  . En appliquant le lemme, on fait varier le nombre de lettres  . 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 de lettres de même type, et on ne peut pas compenser l'accroissement de lettres   et   à la fois, d'où la contradiction.
  • Le langage   n’est pas algébrique. On applique cette fois la variante grammaticale 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 des lettres   itérées, mais aucune lettre  , contradiction.

Langages non algébriques vérifiant le lemme

modifier

Le lemme d'Odgen est une condition nécessaire mais pas suffisante pour les langages algébriques.

  • Le langage   n’est pas algébrique, car étant un langage borné sur un alphabet à deux lettres, son complément (par rapport à  ) est   qui n’est pas algébrique. Pourtant, le langage vérifie le lemme d'Ogden[2].
  • Le langage   n'est pas algébrique, mais le lemme d'Ogden ne permet pas de le prouver parce qu'il n'y a pas moyen d'éviter d'itérer la lettre   initiale [3].

Un langage inhéremment ambigu

modifier
  • 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.

Démonstration de la version grammaticale

modifier

Soit   une grammaire algébrique de variables   et d'axiome  . Soit   un mot qui dérive de  .

La démonstration se trouve simplifiée si on ne veut établir que la version langage du lemme d'itération. Dans ce cas on peut choisir une grammaire sous forme normale de Chomsky, et un arbre de dérivation est essentiellement un arbre binaire.

Un lemme combinatoire

modifier

Considérons un arbre dont certaines feuilles sont distinguées. On dit que :

  • un nœud est distingué lorsque le sous-arbre dont il est racine contient des feuilles distinguée ;
  • un nœud est spécial lorsqu'au moins deux de ses enfants sont distingués.

Le parent d'un nœud distingué est distingué, la racine est distinguée dès que l'une des feuilles est distinguée, un nœud spécial est lui-même distingué.

Un arbre est de degré   si chaque nœud a au plus   enfants.

Lemme — Soit   un arbre de degré   avec   feuilles distinguées. Si chaque branche contient au plus   nœuds spéciaux, alors  .

Démonstration

modifier
 
Découpage du mot  . On reste dans le langage en itérant la partie en couleur car   et   sont des nœuds étiquetés par la même variable  .

On utilise la contraposée du lemme précédent : si l'arbre a strictement plus de   feuilles distinguées, alors l'arbre a au moins une branche qui contient au moins   nœuds spéciaux.

Soit   la longueur maximale des membres droits des règles. On pose   et  . Considérons un arbre de dérivation pour le mot  . Par définition, l'arbre est de degré   et possède des feuilles distinguées qui sont les positions distinguées de  . L'arbre possède une branche ayant au moins   nœuds spéciaux, notés  . Chacun de ces nœuds a au moins un fils distingué qui n'est pas sur la branche ; le nœud est gauche si ce fils est à gauche de la branche, il est droit sinon. Comme  , il y a au moins   sommets distingués soit tous gauches, soit tous droits. Comme ce nombre est supérieur au nombre de variables, deux sommets   et   (notés   et   sur la figure), avec  , sont étiquetés avec la même variable  . L'arbre donne alors les dérivations

 ,   et  .

Si les nœuds distingués sont gauche, les mots   contiennent des positions distinguées, sinon c'est le cas des mots  . Enfin, si le mot   contient plus que   positions distinguées, on recommence le découpage à partir de la racine   de son sous-arbre.

Annexes

modifier

Notes et références

modifier
  1. Ogden 1968.
  2. Luc Boasson et S. Horváth, « On languages satifsfying Ogdens lemma », RAIRO. Informatique théorique, t. 12, no 3,‎ , p. 201-202 (lire en ligne).
  3. Jean Berstel et Luc Boasson, « Context-Free Languages », dans G. Rozenberg, A. Salomaa (éditeurs), Handbook of Theoretical Computer Science, vol. B : Formal Models and Sematics, Elsevier et MIT Press, (ISBN 0-444-88074-7), p. 59-102 —Example 2.5, p. 73.

Bibliographie

modifier
  • William F. Ogden, « A Helpful Result for Proving Inherent Ambiguity », Mathematical Systems Theory, vol. 2, no 3,‎ , p. 191-194 (DOI 10.1007/BF01694004)
  • (en) Marcus Kracht, « Too Many Languages Satisfy Ogden’s Lemma », University of Pennsylvania Working Papers in Linguistics, vol. 10,‎

Articles connexes

modifier