Langage sans étoile
De Wikipedia, l'encyclopédie encyclopedia
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 .