Étoile de Kleene

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Fermeture de Kleene)
Aller à : navigation, rechercher

En théorie des langages, l'étoile de Kleene, parfois appelée fermeture de Kleene ou encore fermeture itérative, est un opérateur unaire utilisé pour décrire les langages formels. Le nom vient de la notation employée : l'étoile est notée par un astérisque.

L'étoile de Kleene est l'un des trois opérateurs de base utilisés pour définir une expression rationnelle, avec la concaténation et l'union ensembliste.

Appliquée à un ensemble , elle a pour résultat le langage , défini ainsi :

  1. Si est un alphabet, c'est-à-dire un ensemble de symboles ou caractères, alors est l'ensemble des mots sur , mot vide inclus.
  2. Si est un langage, alors est le plus petit langage qui le contienne, qui contienne et qui soit stable par concaténation.

Exemples[modifier | modifier le code]

Pour l'alphabet , on a

Pour la partie composée des deux mots et sur l'alphabet , on obtient

Définition[modifier | modifier le code]

On appelle étoile de Kleene d'une partie d'un monoïde le sous-monoïde engendré par . Ce sous-monoïde est noté . Comme d'usage pour les opérations de fermeture, il peut être défini de trois manières équivalentes :

  • est la plus petite partie de contenant et l'élément neutre de et fermée pour l'opération de .
  • est l'intersection de tous les sous-monoïdes de contenant .
  • est l'ensemble de tous les produits de la forme , pour et .

Si est un ensemble générateur du monoïde , on a en particulier .

Cas du monoïde libre[modifier | modifier le code]

Dans le cas d'un alphabet , on note l'ensemble de tous les mots sur . L'ensemble est un monoïde pour la concaténation, et il est engendré par (pour être tout à fait rigoureux, est engendré par les mots composés d'une lettre, que l'on identifie avec les lettres).

Si est une partie de , alors est un sous-monoïde de qui peut être libre ou pas. Il est d'usage de noter par l'ensemble

de tous les produits de éléments de . On a alors la formule

.

Si est un sous-monoïde librement engendré par , c'est-à-dire si tout mot de est produit, de manière unique, de mots de , on dit que est un code ou que est une base de .

Par exemple, l'ensemble est un code, et l'ensemble n'est pas un code parce que le mot possède les deux factorisations

aba= ab . a = a . ba

Opérateur plus[modifier | modifier le code]

L'opérateur plus est un opérateur analogue à l'étoile de Kleene. Il associe à une partie d'un demi-groupe le sous-demi-groupe engendré par , noté . On a

.

Comme d'usage pour l'étoile, l'opérateur plus peut être défini de trois manières équivalentes:

  • est la plus petite partie de contenant et fermée pour l'opération de .
  • est l'intersection de tous les sous-demi-groupes de contenant .
  • est l'ensemble de tous les produits de la forme , pour et .

Dans un monoïde, on a les relations suivantes entre l'étoile et l'opérateur plus:

Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • (en) Stephen C. Kleene, « Representation of events in nerve nets and finite automata », dans Claude E. Shannon et John McCarthy (éditeurs), Automata Studies, Princeton, Princeton University Press, coll. « Annals of Mathematics Studies » (no 34), , viii+285 p. (ISBN 978-0691079165), p. 3-41
  • Jacky Akoka et Isabelle Comyn-Wattiau (éditeurs), Encyclopédie de l'informatique et des systèmes d'information, Paris, Vuibert, , xxxv+1941 p. (ISBN 978-2-7117-4846-4)
  • Olivier Carton, Langages formels, calculabilité et complexité, Vuibert, (ISBN 978-2-7117-2077-4, présentation en ligne)
  • Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, (ISBN 978-2-7117-4807-5)