Fermeture de Kleene

Pour les articles homonymes, voir Fermeture.

La fermeture de Kleene, parfois appelée étoile 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: la fermeture 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 $X$ , elle a pour résultat le langage $X^* - Wikipedia Orange$ , défini ainsi :

Si $X$ est un alphabet, c'est-à-dire un ensemble de symboles ou caractères, alors $X^*$ est l'ensemble des mots sur $X$ , mot vide $\varepsilon - Wikipedia Orange$ inclus.
Si $X$ est un langage, alors $X^*$ est le plus petit langage qui le contienne, qui contienne $\varepsilon - Wikipedia Orange$ et qui soit stable par concaténation.

Exemples

Pour l'alphabet $\{a,b,c\} - Wikipedia Orange$ , on a

$\{a,b,c\}^*=\{\varepsilon, a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,aaa,\ldots\} - Wikipedia Orange$

Pour la partie $X=\{aa,b\}$ composée des deux mots $aa$ et $b$ sur l'alphabet $\{a,b\} - Wikipedia Orange$ , on obtient

$\{aa,b\}^*=\{\varepsilon, b,aa,bb,aab, baa,bbb, aaaa, aabb, baab, bbaa,bbbb,\ldots\} - Wikipedia Orange$

Définition

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

$X^*$ est la plus petite partie de $M$ contenant $X$ et l'élément neutre de $M$ et fermée pour l'opération de $M - Wikipedia Orange$ .
$X^*$ est l'intersection de tous les sous-monoïdes de $M$ contenant $X - Wikipedia Orange$ .
$X^*$ est l'ensemble de tous les produits de la forme $x_1x_2\cdots x_n$ , pour $n\ge0$ et $x_1,x_2,\ldots, x_n\in X - Wikipedia Orange$ .

Si $X$ est un ensemble générateur du monoïde $M$ , on a en particulier $X^*=M - Wikipedia Orange$ .

Cas du monoïde libre

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

Si $X$ est une partie de $A^*$ , alors $X^*$ est un sous-monoïde de $A^*$ qui peut être libre ou pas. Il est d'usage de noter par $X^n - Wikipedia Orange$ l'ensemble

$X^n=\{x_1x_2\cdots x_n\mid x_1,x_2,\ldots, x_n\in X\} - Wikipedia Orange$

de tous les produits de $n$ éléments de $X - Wikipedia Orange$ . On a alors la formule

$X^*=\bigcup_{n\ge0}X^n - Wikipedia Orange$ .

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

Par exemple, l'ensemble $X=\{aa,b\}$ est un code, et l'ensemble $X=\{a,ab,ba\}$ n'est pas un code parce que le mot $aba - Wikipedia Orange$ possède les deux factorisations

$aba=ab\cdot a=a\cdot ab - Wikipedia Orange$ .

Opérateur plus

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

$X^+=\bigcup_{n>0}X^n - Wikipedia Orange$ .

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

$X^+$ est la plus petite partie de $M$ contenant $X$ et fermée pour l'opération de $M - Wikipedia Orange$ .
$X^+$ est l'intersection de tous les sous-demi-groupes de $M$ contenant $X - Wikipedia Orange$ .
$X^+$ est l'ensemble de tous les produits de la forme $x_1x_2\cdots x_n$ , pour $n>0$ et $x_1,x_2,\ldots, x_n\in X - Wikipedia Orange$ .

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

$X^*=X^+\cup\{\varepsilon\}, X^+=XX^*=X^*X. - Wikipedia Orange$

Voir aussi

encyclopédie par wikipédia

Affichages