Fermeture De Kleene

Fermeture De Kleene

Fermeture de Kleene

Page d'aide sur l'homonymie 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 résultat le langage V^\star, défini ainsi :

  1. Si V est un alphabet, c'est-à-dire un ensemble fini de symboles ou caractères, alors V^\star est l'ensemble des mots sur V, mot vide ε inclus.
  2. Si V est un langage, alors V^\star est le plus petit langage qui le contienne, qui contienne {ε} et qui soit stable par concaténation (la concaténation de deux éléments de V^\star est également dans V^\star).

Exemple d'application de l'étoile de Kleene à un alphabet :

{'a', 'b', 'c'}* = {ε, « a », « b », « c », « aa », « ab », « ac », « ba », « bb », « bc », ...}

Exemple d'application de l'étoile de Kleene à un langage :

{« ab », « c »}* = {ε, « ab », « c », « abab », « abc », « cab », « cc », « ababab », « ababc », « abcab », « abcc », « cabab », « cabc », « ccab », « ccc », ...}

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.

On généralise souvent l'étoile de Kleene à tout monoïde (M,.), où V^\star, avec V\subset M, désigne la clôture de V par la loi « . », à laquelle on joint ε, l'élément neutre du monoïde. En d'autres termes V^\star est le plus petit ensemble contenant V \cup \{\epsilon\}, et stable par « . ». Il s'agit effectivement d'une généralisation, car l'ensemble des mots sur un alphabet est un monoïde dont la loi de composition interne est la concaténation, et l'élément neutre est le mot vide.

Voir aussi

  • Portail des mathématiques Portail des mathématiques
  • Portail de l’informatique Portail de l’informatique
  • Portail de la logique Portail de la logique
Ce document provient de « Fermeture de Kleene ».

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. Le nom vient de la notation employée: la… …   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

Share the article and excerpts

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