Lemme d'Ogden

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. 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. É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 : Le plus petit entier pour lequel l'énoncé est vrai est appelé 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, et notamment pour les langages inhéremment ambigus. Voici l'énoncé : 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. 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.