L'étoile de Kleene, parfois appelée fermeture de Kleene ou encore fermeture itérative, est, en théorie des langages, un opérateur unaire utilisé pour décrire les langages formels. Le nom étoile vient de la notation employée, un astérisque, et Kleene de Stephen Cole Kleene qui l'a introduite. 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 : Si est un alphabet, c'est-à-dire un ensemble de symboles ou caractères, alors est l'ensemble des mots sur , mot vide inclus. Si est un langage, alors est le plus petit langage qui le contienne, qui contienne et qui soit stable par concaténation. Pour l'alphabet , on a Pour la partie composée des deux mots et sur l'alphabet , on obtient 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 . 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 .

À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Cours associés (2)
CS-320: Computer language processing
We teach the fundamental aspects of analyzing and interpreting computer languages, including the techniques to build compilers. You will build a working compiler from an elegant functional language in
CS-101: Advanced information, computation, communication I
Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a
Concepts associés (18)
Monoïde
En mathématiques, un monoïde est une structure algébrique utilisée en algèbre générale, définie comme un ensemble muni d'une loi de composition interne associative et d'un élément neutre. Autrement dit, c'est un magma associatif et unifère, c'est-à-dire un demi-groupe unifère. Il arrive parfois qu'une structure composée d'un ensemble et d'une unique opération soit relativement pauvre en éléments inversibles, par exemple un anneau où l'on considère uniquement la multiplication. Une telle structure est appelée monoïde.
Free monoid
In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero elements, often called the empty string and denoted by ε or λ, as the identity element. The free monoid on a set A is usually denoted A∗. The free semigroup on A is the subsemigroup of A∗ containing all elements except the empty string. It is usually denoted A+.
Chaîne de caractères
En informatique, une chaîne de caractères est à la fois conceptuellement une suite ordonnée de caractères et physiquement une suite ordonnée d' unités de code (code unit). La chaîne de caractères est un type de donnée dans de nombreux langages informatiques. La traduction en anglais est string. À l'époque des pionniers, on a communément confondu chaîne de caractères et chaîne d'octets, ce qui prête aujourd'hui à confusion, lorsque l'on ne veut pas se limiter à 255 caractères.
Afficher plus

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.