Théorème de l'étoile

Théorème de l'étoile

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 Théorème de l'étoile de Wikipédia en français (auteurs)

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

Regardez d'autres dictionnaires:

  • Etoile — Étoile Pour les articles homonymes, voir Étoile (homonymie). Le Soleil, l’étoile la plus proche de la Terre, en train de « se lever » ; ce n est que …   Wikipédia en Français

  • Theoreme de Kennelly — Théorème de Kennelly Présentation des montages sous forme de triangle (à gauche) et d étoile (à droite). Le théorème de Kennelly, ou transformation triangle étoile, ou transformation Y Δ, ou encore transformation T Π, est une technique… …   Wikipédia en Français

  • Théorème de kennelly — Présentation des montages sous forme de triangle (à gauche) et d étoile (à droite). Le théorème de Kennelly, ou transformation triangle étoile, ou transformation Y Δ, ou encore transformation T Π, est une technique mathématique qui permet de… …   Wikipédia en Français

  • Théorème de darboux (géométrie) — Le théorème de Darboux est un théorème central de la géométrie symplectique : les variétés symplectiques de dimension 2n sont deux à deux localement symplectomorphes. Plus explicitement : Théorème de Darboux   Si (M,ω) est une …   Wikipédia en Français

  • Theoreme de Kleene — Théorème de Kleene En théorie des automates, le théorème de Kleene affirme qu un langage est rationnel si et seulement s’il est reconnu par un automate fini. Ce théorème est dû à Stephen Kleene. C est un théorème essentiel des langages formels,… …   Wikipédia en Français

  • Théorème de kleene — En théorie des automates, le théorème de Kleene affirme qu un langage est rationnel si et seulement s’il est reconnu par un automate fini. Ce théorème est dû à Stephen Kleene. C est un théorème essentiel des langages formels, puisqu il fait le… …   Wikipédia en Français

  • Théorème de Kleene —  Ne doit pas être confondu avec Théorème de récursion de Kleene ni Théorème du point fixe de Kleene. En informatique théorique, et plus précisément en théorie des automates, le théorème de Kleene affirme qu un langage peut être décrit par… …   Wikipédia en Français

  • Étoile — Pour les articles homonymes, voir Étoile (homonymie). Le Soleil, l’étoile la plus proche de la Terre …   Wikipédia en Français

  • Théorème de Kennelly — Présentation des montages sous forme de triangle (à gauche) et d étoile (à droite). Le théorème de Kennelly, ou transformation triangle étoile, ou transformation Y Δ, ou encore transformation T Π, est une technique mathématique qui permet de… …   Wikipédia en Français

  • Théorème de restriction cristallographique — Le théorème de restriction cristallographique est basé sur l observation du fait que les opérations de symétrie rotationnelles d un cristal sont limitées à des opérations d ordre 1, 2, 3, 4 et 6. Cependant, les quasi cristaux, découverts en 1984 …   Wikipédia en Français

Share the article and excerpts

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