Langage sans étoile

En informatique théorique, et notamment en théorie des langages formels, un langage rationnel est sans étoile (star-free language en anglais) s'il peut être obtenu à partir des lettres d'un alphabet et de l'ensemble vide par un ensemble fini d'opérations ensemblistes d'union, intersection, de complémentaire et de concaténations, mais sans utiliser l'opération étoile. Par exemple, l'ensemble de tous les mots est le complémentaire de l'ensemble vide : c'est donc un langage sans étoile. Le langage des mots sur l'alphabet qui ne contiennent pas deux lettres consécutives est aussi un langage sans étoile. En effet, c'est l'ensemble défini par , où dénote le complément d'une partie de . La famille des langages sans étoiles est la plus petite famille de langages formels : qui contient l'ensemble vide et tous les singletons composés d'une lettre. et qui est stable par union, complémentaire et concaténation. De manière équivalente, les langages sans étoile sont ceux qui admettent une expression régulière pouvant contenir des constructions pour le complémentaire mais pas d'étoile. Comme les langages rationnels généraux sont fermés par complémentation, on voit que les langages sans étoile sont un sous-ensemble des langages rationnels. Les langages suivants sont sans étoile. Le langage contenant tous les mots sur un alphabet , parce qu'il est le complémentaire de l'ensemble vide : ; L'ensemble {ε} réduit au mot vide est sans étoile : c'est le complément de ; tous les langages finis sont également des langages sans étoile. Sur , le langage est sans étoile Tout langage local est sans étoile. Le langage sur une seule lettre n'est pas un langage sans étoile, comme montré plus bas. Un théorème dû à Marcel-Paul Schützenberger caractérise les langages sans étoile de manière algébrique, à travers leur monoïde syntaxique. Cette caractérisation est intéressante par le lien qu'elle établit entre une définition combinatoire et une propriété algébrique ; elle est de plus utile pour montrer qu'un langage n’est pas sans étoile.