Lemme d'Ogden

Un article de Wikipédia, l'encyclopédie libre.
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

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.

[modifier] Énoncé

[modifier] Forme simplifiée

Soit L un langage algébrique. Il existe un entier k tel que tout mot w \in L de longueur \left|w\right| \geq k se factorise en w = αuβvγ, avec :

  1. u \neq \epsilon ou v \neq \epsilon ;
  2. \left|u \beta v\right| \leq k ;
  3. \forall j, \quad \alpha u^j \beta v^j \gamma \in L.

[modifier] Lemme d'Ogden

Soit L un langage algébrique, et soit G une grammaire telle que LG(S) = L. Soit \hat L_G(S) = \{ w \in (A+V)^* \big\vert S \rightarrow^* w \} le langage des « étapes de dérivation » à partir de S (i.e. des chaînes de symboles grammaticaux dérivables à partir de S). Il existe un entier k tel que tout mot w de \hat L_G(S) dont on a marqué au moins k lettres admette une factorisation w = αuβvγ vérifiant :

  1. α, u et β ou β, v et γ contiennent des lettres marquées ;
  2. uβv contient moins de k lettres marquées ;
  3. il existe un non-terminal T tel que
    • S \rightarrow^* \alpha T \gamma
    • T \rightarrow^* u T v
    • T \rightarrow^* \beta.