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 de longueur se factorise en w = αuβvγ, avec :
- ou ;
- ;
- .
[modifier] Lemme d'Ogden
Soit L un langage algébrique, et soit G une grammaire telle que LG(S) = L. Soit 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 dont on a marqué au moins k lettres admette une factorisation w = αuβvγ vérifiant :
- α, u et β ou β, v et γ contiennent des lettres marquées ;
- uβv contient moins de k lettres marquées ;
- il existe un non-terminal T tel que
- .