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 *$ , 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 $ε$ inclus.
Si $X$ est un langage, alors $X *$ est le plus petit langage qui le contienne, qui contienne $ε$ et qui soit stable par concaténation.

Exemples

Pour l'alphabet ${a, b, c}$ , on a

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

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

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

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 *$ . 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$ .
$X *$ est l'intersection de tous les sous-monoïdes de $M$ contenant $X$ .
$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$ .

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

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 *$ 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$ l'ensemble

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

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

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

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 *$ .

Par exemple, l'ensemble $X = {a a, b}$ est un code, et l'ensemble $X = {a, a b, b a}$ n'est pas un code parce que le mot $a b a$ possède les deux factorisations

$aba=ab\cdot a=a\cdot ab$ .

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 +$ . On a

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

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$ .
$X +$ est l'intersection de tous les sous-demi-groupes de $M$ contenant $X$ .
$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$ .

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.$

Voir aussi

Catégories :

Wikimedia Foundation. 2010.

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

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

Regardez d'autres dictionnaires:

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. Appliquée à un ensemble V, elle a pour… … Wikipédia en Français
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. Appliquée à un ensemble V, elle a pour… … Wikipédia en Français
Kleene — Stephen Cole Kleene Stephen Cole Kleene (né le 5 janvier 1909 à Hartford, mort le 25 janvier 1994) est un mathématicien et logicien américain. Biographie et contribution scientifique Kleene est connu pour avoir fondé la branche de la logique… … Wikipédia en Français
Fermeture — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Fermeture », sur le Wiktionnaire (dictionnaire universel) Le terme fermeture renvoie à :… … Wikipédia en Français
Fermeture (mathématiques) — Clôture (mathématiques) On parle de clôture ou de fermeture en mathématiques dans des contextes très divers. Quelques exemples sont listés ci dessous. Clôture pour des opérations En mathématiques, on dit qu un ensemble est clos pour des fonctions … Wikipédia en Français
Étoile de Kleene — 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. Appliquée à un ensemble V … Wikipédia en Français
Stephen Cole Kleene — Kleene en 1978 Stephen Cole Kleene – né le 5 janvier 1909 à Hartford (Connecticut) et mort le 25 janvier 1994 à Madison (Wisconsin) – est un mathématicien et logicien américain. Biographie et contribution scientifique Klee … Wikipédia en Français
Algebre de Kleene — Algèbre de Kleene En mathématiques, une algèbre de Kleene (du nom du logicien américain Stephen Cole Kleene) correspond à l un des deux concepts suivants : Un treillis ordonné et distributif avec une involution satisfaisant les lois de De… … Wikipédia en Français
Algèbre De Kleene — En mathématiques, une algèbre de Kleene (du nom du logicien américain Stephen Cole Kleene) correspond à l un des deux concepts suivants : Un treillis ordonné et distributif avec une involution satisfaisant les lois de De Morgan et l… … Wikipédia en Français
Algèbre de Kleene — Pour les articles homonymes, voir Algèbre (homonymie). En mathématiques, une algèbre de Kleene (du nom du logicien américain Stephen Cole Kleene) correspond à l un des deux concepts suivants : Un treillis ordonné et distributif avec une… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Fermeture de Kleene

Sommaire

Définition

Cas du monoïde libre

Opérateur plus

Voir aussi

Regardez d'autres dictionnaires:

Share the article and excerpts

Dictionnaires et Encyclopédies sur 'Academic'

Wikipédia en Français

Fermeture de Kleene

Sommaire

Définition

Cas du monoïde libre

Opérateur plus

Voir aussi

Regardez d'autres dictionnaires:

Share the article and excerpts

Direct link