Lemme d'ogden

Lemme d'ogden

Lemme d'Ogden

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.

Énoncé

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.

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.
Ce document provient de « Lemme d%27Ogden ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Lemme d'ogden de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Lemme d'Ogden — 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. Le lemme d Ogden est une version plus élaborée du lemme d itération… …   Wikipédia en Français

  • Lemme de l'étoile — En théorie des langages, le lemme de l étoile (ou encore lemme d itération, lemme de pompage, lemme de la pompe, pumping lemma en anglais) énonce une propriété typique de tout langage rationnel. Informellement, il stipule que tout mot… …   Wikipédia en Français

  • Lemme d'itération pour les langages algébriques — Le Lemme d itération pour les langages algébriques, aussi connu sous le vocable Lemme de Bar Hillel, Perles et Shamir, donne une condition de répétition nécessaire pour les langages algébriques. Sa version simplifiée pour les langages rationnels… …   Wikipédia en Français

  • Lemme d'itération —  Ne pas confondre avec le Théorème d itération. En informatique théorique, et spécialement en théorie des langages, un lemme d itération (pumping lemma en anglais) est un énoncé qui stipule que, dans un langage formel d une classe… …   Wikipédia en Français

  • Langage algébrique — En théorie des langages formels, un langage algébrique ou langage non contextuel est un langage qui peut être engendré par une grammaire algébrique. De manière équivalente un langage algébrique est un langage reconnu par automate à pile. Les… …   Wikipédia en Français

  • Grammaire non contextuelle — En linguistique et en informatique, une grammaire non contextuelle, grammaire hors contexte ou grammaire algébrique (type 2 dans la hiérarchie de Chomsky) est une grammaire formelle dans laquelle chaque règle de production (ou simplement… …   Wikipédia en Français

  • 2002 in film —             List of years in film       (table) … 1992 .  1993 .  1994 .  1995  . 1996  . 1997  . 1998 … 1999 2000 2001 2002 2003 2004 2005 …  …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”