Voir la source de Lemme d'Ogden

{{article général|Lemme d'itération pour les langages algébriques}}
En [[informatique théorique]], le '''lemme d'Ogden''' est un [[Lemme (mathématiques)|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 [[langage algébrique|algébriques]]. Il est nommé ainsi d'après William F. Ogden, un [[informatique théorique | informaticien théoricien]] [[États-Unis | américain]] qui l’a publié en 1968<ref>{{harvsp|Ogden|1968|p=}}.</ref>.

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 [[Grammaire ambigüe|inhéremment ambigus]].

== Énoncés ==

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

{{Théorème|Lemme d'Ogden|Soit <math>L</math> un [[langage algébrique]]. Il existe un entier <math>N</math> tel que pour tout mot <math>w</math> de <math>L</math> de longueur <math>|w|\ge N</math>, et pour tout choix de <math>N</math> positions distinguées dans <math>w</math>, il existe une factorisation  <math>w=xuyvz</math> telle que :
# (<math>x</math> et <math>u</math> et <math>y</math>) ou (<math>y</math> et <math>v</math> et <math>z</math>) contiennent au moins une position distinguée ;
# <math>uyv</math> contient au plus <math>N</math> positions distinguées ;
# <math>xu^nyv^nz \in L</math> pour tout <math>n\ge0</math>.}} 

Le plus petit entier <math>N</math> pour lequel l'énoncé est vrai est appelé la ''constante d'Ogden''.

=== Variante grammaticale ===

Il existe une variante grammaticale du lemme d'Ogden : elle dit que la [[Lemme d'itération pour les langages algébriques#Énoncé formel |paire itérante]] <math>(x,u,y,v,z)</math> peut être choisie ''grammaticale''.  Cette variante est bien utile dans certains cas, et notamment pour les langages inhéremment ambigus. Voici l'énoncé :

{{Théorème|nom=Lemme d'Ogden (variante grammaticale)|1=Soit <math>G</math> une [[grammaire algébrique]] d'axiome <math>S</math>. Il existe un entier <math>N</math> tel que pour tout mot <math>w</math> qui dérive de <math>S</math> de longueur <math>|w|\ge N</math>, et pour tout choix de au moins <math>N</math> positions distinguées dans <math>w</math>, il existe une factorisation  <math>w=xuyvz</math> telle que :
# (<math>x</math> et <math>u</math> et <math>y</math>) ou (<math>y</math> et <math>v</math> et <math>z</math>) contiennent au moins une position distinguée ;
# <math>uyv</math> contient au plus <math>N</math> positions distinguées ;
# Il existe une variable <math>X</math> telle que <math>S\stackrel{*}\to xXz,\ X\stackrel{*}\to uXv,\ X\stackrel{*}\to y</math>.}}

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

== Exemples d'application ==

=== Langages non algébriques ===
* Le langage <math>L=\{a^n b^n c^n \mid n \geqslant 0\}</math> n'est pas algébrique. Pour le voir, on distingue dans le mot  <math>a^N b^N c^N</math> les lettres égales à <math>a</math>. En appliquant le lemme, on fait varier le nombre de lettres <math>a</math>. Il faut distinguer encore le cas où le facteur <math>v</math> 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 <math>b</math> et <math>c</math> à la fois, d'où la contradiction.

* Le langage <math>L=\{a^mb^nc^md^n\mid n,m\ge0\}</math> n’est pas algébrique. On applique cette fois  la variante grammaticale du lemme au mot <math>w  = a^Nb^Nc^Nd^N</math>, où <math>N</math> est la constante d'Ogden, et où les lettres distinguées sont les lettres <math>b</math>. Il existe des dérivations 
::<math>S\stackrel{*}\to  a^Nb^kXd^\ell , \ X\stackrel{*}\to  b^iXd^i, \ X\stackrel{*}\to  b^{\bar k}c^Nd^{\bar \ell}</math>
:avec <math>N=k+i+\bar k=\ell+i+\bar\ell</math>. On applique le lemme une deuxième fois, au mot <math>a^Nb^kXd^\ell</math>, où cette fois-ci ce sont les lettres <math>a</math> qui sont distinguées. On obtient une paire itérante contenant des lettres <math>a</math> itérées, mais aucune lettre <math>d</math>, contradiction.

=== Langages non algébriques vérifiant le lemme ===
Le lemme d'Odgen est une condition nécessaire mais pas suffisante pour les langages algébriques.
* Le langage <math>L=\{a^nb^m\mid n\ne m\}\cup\{a^nb^n \mid n\text{ non premier }\}</math> n’est pas algébrique, car étant un langage borné sur un alphabet à deux lettres, son complément (par rapport à <math>a^*b^*</math>) est <math>\{a^nb^n \mid n\text{  premier }\}</math> qui n’est pas algébrique. Pourtant, le langage vérifie le lemme d'Ogden<ref>{{Article
|langue=
|auteur1= Luc Boasson|auteur2= S. Horváth
|titre= On languages satifsfying Ogdens lemma
|périodique= RAIRO. Informatique théorique
|tome=12
|numéro=3
|date=1978
|pages=201-202
|issn=
|lire en ligne= http://www.numdam.org/article/ITA_1978__12_3_201_0.pdf
}}.</ref>.
* Le langage <math>L=b^*\cup aaa^*b^*\cup \{ab^p\mid p\text{ premier }\}</math> 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 <math>a</math> initiale <ref>{{chapitre | auteur1 = Jean Berstel|auteur2 = Luc Boasson | titre chapitre = Context-Free Languages | auteurs ouvrage = G. Rozenberg, A. Salomaa (éditeurs) | titre ouvrage = Handbook of Theoretical Computer Science | éditeur = Elsevier et MIT Press | année = 1990 | volume = B | titre volume = Formal Models and Sematics | passage = 59-102 | isbn = 0-444-88074-7 }} —Example 2.5, {{p.|73}}.</ref>.

=== Un langage inhéremment ambigu ===

* Le langage <math>L=\{a^nb^nc^m\mid n,m\ge0\}\cup \{a^mb^nc^n\mid n,m\ge0\}</math> est inhéremment ambigu. Un langage est ''[[grammaire algébrique|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 {{retrait|<math>w  = a^Nb^Nc^{N+N!}</math>}} où <math>N</math> est la constante d'Ogden, et en distinguant les lettres <math>b</math>. Il existe une dérivation {{retrait|<math>S\stackrel{*}\to  xXz\stackrel{*}\to  xuXvz\stackrel{*}\to  xuyvz</math>,}} et les conditions impliquent que <math>u=a^i</math> et <math>v=b^i</math> pour un entier <math>0\le i\le N</math>. En itérant <math>N!/i</math> fois la dérivation {{retrait|<math>X\stackrel{*}\to  uXv</math>}} on obtient un arbre de dérivation pour le mot <math>a^{N+N!}b^{N+N!}c^{N+N!}</math>. Cet arbre contient un sous-arbre dont la frontière ne contient que des lettres <math>a</math> et <math>b</math>, dont au moins <math>N!-N</math> lettres <math>b</math>. En appliquant le même procédé au mot {{retrait|<math>w  = a^{N+N!}b^Nc^N</math>,}} on obtient un autre arbre de dérivation pour le même mot  <math>a^{N+N!}b^{N+N!}c^{N+N!}</math>. Cet arbre contient un sous-arbre dont la frontière ne contient que des lettres <math>b</math> et <math>c</math>, dont au moins <math>N!-N</math> lettres <math>b</math>. Cet arbre est donc différent du premier arbre.

== Démonstration de la version grammaticale ==
Soit <math>G</math> une [[grammaire algébrique]] de variables <math>V</math> et d'axiome <math>S</math>. Soit <math>w</math> un mot qui dérive de <math>S</math>.

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 ===
<!-- [[Fichier:Arbre de dérivation.gif|vignette|upright=1|Un arbre de dérivation avec des nœuds distinguées (d) et des nœuds spéciaux (e).]] -->
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é <math>m</math> si chaque nœud a au plus <math>m</math> enfants.

{{théorème|nom=Lemme|énoncé=Soit <math>t</math> un arbre de degré <math>m</math> avec <math>k</math> feuilles distinguées. Si chaque branche contient au plus <math>r</math> nœuds spéciaux, alors <math>k\le m ^r</math>.}}

{{démonstration | déroulante=oui | contenu=
Si <math>r=0</math>, il n'y a pas de nœud spécial ; il n'y a qu'une seule feuille distinguée, car s'il y en avait deux, leur ancêtre commun serait spécial. 
Supposons donc <math>r\ge1</math>, et soit <math>x</math> un nœud spécial dont aucun descendant n’est spécial ; chacun des sous-arbres de <math>x</math> contient au plus une feuille distinguée, et comme <math>x</math> a au plus <math>m</math> enfants, l'arbre de racine <math>x</math> contient au plus <math>m</math> feuilles distinguées. On remplace maintenant chaque sous-arbre de cette nature une simple feuille distinguée. Le nombre de nœuds spéciaux diminue de 1 sur chaque branche. L'arbre obtenu a, par récurrence, au plus <math>m^{r-1}</math> feuilles distinguées. Comme chacune des nouvelles feuilles a remplacé un sous-arbre avec au plus <math>m</math> feuilles, ceci prouve le résultat.}}

=== Démonstration ===
[[Fichier:Découpage du mot.jpg|vignette|Découpage du mot <math>w
</math>. On reste dans le langage en itérant la partie en couleur car <math>b_1</math> et <math>b_2</math> sont des nœuds étiquetés par la même variable <math>X</math>.]]
On utilise la contraposée du lemme précédent : si l'arbre a strictement plus de <math>m^r</math> feuilles distinguées, alors l'arbre a au moins une branche qui contient au moins <math>1+r</math> nœuds spéciaux.

Soit <math>m</math> la longueur maximale des membres droits des règles. On pose <math>r=2(|V|+1)</math> et <math>N=1+m^r</math>.  Considérons un arbre de dérivation pour le mot <math>w</math>. Par définition, l'arbre est de degré <math>m</math> et possède des feuilles distinguées qui sont les positions distinguées de <math>w</math>. L'arbre possède une branche ayant au moins <math>1+r</math> nœuds spéciaux, notés <math>s_0,\ldots,s_r</math>.
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 <math>1+r=2|V|+3</math>, il y a au moins <math>|V|+2</math> sommets distingués  soit tous gauches, soit tous droits. Comme ce nombre est supérieur au nombre de variables, deux sommets <math>s_i</math> et <math>s_j</math> (notés <math>b_1</math> et <math>b_2</math> sur la figure), avec <math>i<j</math>, sont étiquetés avec la même variable <math>X</math>. L'arbre donne alors les dérivations 
: <math>S \stackrel{*}\to xXz</math>, <math>X \stackrel{*}\to uXv</math> et <math>X \stackrel{*}\to y</math>. 
Si les nœuds distingués sont gauche, les mots <math>x, u, y</math> contiennent des positions distinguées, sinon c'est le cas des mots <math>y, v, z</math>. Enfin, si le mot <math>y</math> contient plus que <math>N</math> positions distinguées, on recommence le découpage à partir de la racine <math>s_j</math> de son sous-arbre.

== Annexes ==
=== Notes et références ===
{{Références}}

=== Bibliographie ===
* {{Article
 | prénom1         = William F.
 | nom1            = Ogden
 | titre           = A Helpful Result for Proving Inherent Ambiguity
 | périodique      = Mathematical Systems Theory
 | lien périodique = 
 | volume          = 2
 | numéro          = 3
 | année           = 1968
 | pages           = 191-194
 |doi=10.1007/BF01694004
}}

* {{Langages formels, calculabilité et complexité}} {{plume}}

* {{Article
 | langue=english
 |auteur1=| prénom1         = Marcus
 | nom1            = Kracht
 | titre           = Too Many Languages Satisfy Ogden’s Lemma
 |périodique=University of Pennsylvania Working Papers in Linguistics
 | volume          = 10
 | année           = 2004
|date=|lire en ligne=|pages=}}

=== Articles connexes ===
* [[Grammaire algébrique]]
* [[Langage algébrique]]
* [[Lemme d'itération pour les langages algébriques]]

{{Palette Informatique théorique}}

{{portail|langues|Informatique|Informatique théorique}}

[[Catégorie:Langage formel|Lemme d'Ogden]]
[[Catégorie:Théorème d'informatique|Ogden]]