Lemme de l'etoile

Lemme de l'etoile

Lemme de l'étoile

En théorie des langages, le lemme de l'étoile (ou encore lemme d'itération, lemme de pompage, pumping lemma en anglais) décrit une propriété essentielle de tout langage rationnel. Informellement, il établit que tout mot suffisamment long d'un langage rationnel peut être pompé, c'est-à-dire qu'une partie centrale du mot peut être répétée un nombre arbitraire de fois pour produire un nouveau mot qui se trouve encore dans le langage initial.

Le lemme de l'étoile a été imaginé pour la première fois par Y. Bar-Hillel, M. Perles, E. Shamir en 1961.[1] Il est très pratique pour montrer qu'un langage donné n'est pas rationnel (en raisonnant par l'absurde).

Sommaire

Énoncé formel

Soit L un langage rationnel sur l'alphabet X.

Alors il existe un entier p tel que :

\forall w \in L, |w| \geqslant p \Rightarrow \exist x,y,z \in X^*,

  1. w = xyz,
  2. y \neq \epsilon,
  3. |xy| \leqslant p
  4. \forall n \in \mathbb{N}, xy^nz \in L.

| w | désigne la longueur du mot w. L'entier p ne dépend que de L et est parfois appelé "longueur de pompage". (1) signifie que w est divisé en trois facteurs ; (2) signifie que y doit être de longueur au moins 1 ; (3) signifie que la "pompe" y doit se trouver dans les p premières lettres de w. Il n'y a pas de restrictions sur x et z.

Une application du lemme de l'étoile

Le lemme de l'étoile est souvent utilisé pour démontrer qu'un langage donné n'est pas rationnel. La preuve se fait en général par l'absurde, en supposant que le langage est rationnel et en exhibant un mot du langage de longueur suffisante tel que la propriété (4) du lemme n'est pas vérifiée.

Prenons par exemple le langage L = \{a^n b^n / n \in \mathbb{N} \} sur l'alphabet Σ = {a,b}. Supposons par l'absurde que L est rationnel. On fixe l'entier p apparaissant dans l'énoncé du lemme. On choisit le mot w = apbp. Il existe donc une décomposition(d´apres la condition (1) du lemme) w = xyz vérifiant les conditions (2), (3), (4)du lemme de l'étoile. | xy | < p donc il existe deux entiers i et j tels que i + j < p et x = ai,y = aj. De plus j > 0 car y n'est pas le mot vide. Il en résulte que z = ap − i − jbp. On devrait ainsi avoir xz = xy^0z = a^{p-j}b^p \in L, ce qui est absurde car p − j < p. Donc L n'est pas rationnel.

On montre de même que

  • le langage des palindromes sur Σ = {a,b} n'est pas rationnel,
  • le langage L' = \{ w \in X^* / |w|_a = |w|_b \} sur Σ = {a,b} n'est pas rationnel (où | w | a désigne le nombre d'occurrences de la lettre a dans le mot w).

Considérations intuitives

Voici un automate fini reconnaissant le langage décrit par l'expression rationnelle a(bc)*d.

L'automate fini reconnaît le mot abcbcd. Comme il contient plus de lettres que le nombre d'états de l'automate, tout chemin étiqueté par abcbcd dans l'automate comportera au moins un état répété. Ici, l'état q1 est répété. On comprend ainsi que ad appartient au langage reconnu par l'automate, en empruntant le chemin q_0 \overset{a}{\longrightarrow} q_1 \overset{d}{\longrightarrow} q_3 . De même, en répétant la boucle bc, tout mot de la forme a(bc)nd avec n \in \mathbb{N} sera reconnu par l'automate.

On pressent donc que la démonstration reposera sur le nombre d'état d'un automate reconnaissant le langage rationnel en question, et sur la répétition d'états lors de la lecture d'un mot.

Preuve du lemme de l'étoile

Rappel : si L est un langage rationnel, alors il existe un automate fini reconnaissant le langage L.

On considère un langage rationnel L.

Premier cas : si L est fini, alors on choisit p > \max_{w \in L} |w| . Alors il n'existe pas de mot w appartenant à L tel que |w| \geqslant p , donc l'assertion à vérifier est triviale.


Deuxième cas : si L est infini.
Il existe un automate fini A qui reconnaît L. Le nombre d'états de A étant fini, on note p ce nombre augmenté de 1.
Soit maintenant w un mot de L tel que |w| \geqslant p . w est reconnu par A, donc il existe un chemin q_0 \overset{w}{\longrightarrow} q_n réussi dans A, étiqueté par w. Autrement dit, q0 est un état initial de A, et en partant de cet état on peut lire l'une après l'autre toutes les lettres de w en terminant la lecture par un état qn acceptant de A. Ceci impose n = |w| \geqslant p , ce qui assure par la définition de p qu'un certain état q = q_i, \ i \in \{ 0 .. n \} intervient au moins deux fois dans le chemin parcouru pour lire w.
On peut choisir i minimal. q est ainsi décrit comme la première occurrence du premier état q répété au cours du chemin q_0 \longrightarrow q_n . On note alors y le mot qui est lu entre qi et qj, la deuxième occurrence de q dans le chemin en question (avec donc n \geqslant j > i ). On note x le mot lu entre q0 et qi, et z le mot lu entre qj et qn. Ainsi, w = xyz.
On remarque que x et z peuvent être vides, mais y ne l'est pas. Vu la définition de y, la propriété (4) du lemme est vérifiée. Quant à la propriété (2), elle résulte des choix de i et j.

Une condition nécessaire mais non suffisante

Il faut bien saisir que le lemme ne donne qu'une condition nécessaire. La contraposée de ce lemme nous dit donc qu'un langage ne vérifiant pas les propriétés énoncées n'est pas rationnel, mais en aucun cas on ne peut affirmer qu'un langage non rationnel ne vérifiera pas ces propriétés. Il s'agit d'un problème d'implication logique, entre autres :

  • Si le lemme est faux pour un langage donné, alors ce langage n'est pas rationnel
  • Si le lemme est vrai pour un langage donné, alors ce langage peut ne pas être rationnel

Par exemple, notons uR l'image miroir d'un mot quelconque u. uR est donc tel que uuR est un palindrome. Le langage L = \{ uu^Rv,\ u,v \in \{a,b\}^+\} n'est pas rationnel et vérifie le lemme. Plus explicitement, L est le langage des mots constitués d'un palindrome non vide suivi d'un mot non vide sur l'alphabet {a,b}.
Prenons p = 4, et w = uuRv de longueur au moins 4. Si u est de longueur 1, alors v est de longueur au moins 2, et on choisit pour y la première lettre de v par exemple. Sinon, u est de longueur au moins 2 et on prend pour y la première lettre de u, z les lettres restantes et x le mot vide : on remarque que pour k \geqslant 2, \ y^k commence par le palindrome non vide yy.

Voir aussi

Notes et références

  1. ↑ Y. Bar-Hillel, M. Perles, E. Shamir, "On formal properties of simple phrase structure grammars", Zeitschrift für Phonetik, Sprachweissenshaft und Kommunikationsforschung 14 (1961) pp. 143-172.
  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Lemme de l%27%C3%A9toile ».

Wikimedia Foundation. 2010.

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

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Lemme De L'étoile — En théorie des langages, le lemme de l étoile (ou encore lemme d itération, lemme de pompage, pumping lemma en anglais) décrit une propriété essentielle de tout langage rationnel. Informellement, il établit que tout mot suffisamment long d un… …   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 de pompage — Lemme de l étoile En théorie des langages, le lemme de l étoile (ou encore lemme d itération, lemme de pompage, pumping lemma en anglais) décrit une propriété essentielle de tout langage rationnel. Informellement, il établit que tout mot… …   Wikipédia en Français

  • 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… …   Wikipédia en Français

  • Etoile (homonymie) — Étoile (homonymie) Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom …   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

  • Lemme (mathématiques) — Le lemme, en mathématiques et en logique mathématique, est un résultat intermédiaire sur lequel on s appuie pour conduire la démonstration d un théorème plus important. Principe En effet, la méthode de démonstration d un théorème est souvent la… …   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'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

  • Étoile (homonymie) — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Étoile (homonymie) », sur le Wiktionnaire (dictionnaire universel) Sommaire …   Wikipédia en Français

Share the article and excerpts

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