Langage sans étoile

En informatique théorique, et notamment en théorie des langages formels, un langage rationnel est sans étoile (Modèle:Langue 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 $\{a,b\}$ qui ne contiennent pas deux lettres $a$ consécutives est aussi un langage sans étoile. En effet, c'est l'ensemble défini par $({\mathrm{\varnothing }}^{c}aa{\mathrm{\varnothing }}^c{)}^c$, où $X^c$ dénote le complément d'une partie $X$ de $\{a,b{\}}^{*}$.

Définition

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.

Autres exemples et contre-exemples

Les langages suivants sont sans étoile.

• Le langage ${\mathrm{\Sigma }}^{*}$contenant tous les mots sur un alphabet $\mathrm{\Sigma }$, parce qu'il est le complémentaire de l'ensemble vide : ${\mathrm{\Sigma }}^{*}={\mathrm{\varnothing }}^c$ ;
• L'ensemble {ε} réduit au mot vide est sans étoile : c'est le complément de ${\mathrm{\Sigma }}^{*}\mathrm{\Sigma }$;
• tous les langages finis sont également des langages sans étoile.
• Sur $\mathrm{\Sigma }=\{a,b\}$, le langage $(ab{)}^{+}=(a{\mathrm{\Sigma }}^{*}\cap {\mathrm{\Sigma }}^{*}b)\setminus {\mathrm{\Sigma }}^{*}(aa+bb){\mathrm{\Sigma }}^{*}$ est sans étoile
• Tout langage local est sans étoile.
• Le langage $L=(aa{)}^{*}$ sur une seule lettre n'est pas un langage sans étoile, comme montré plus bas.

Caractérisations

Théorème de Schützenberger

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. Il est en effet difficile de montrer, sans elle, qu'un langage donné n'est pas un langage sans étoile car la définition par expression rationnelle demande de passer en revue toutes les expressions rationnelles sans étoile pour affirmer que le langage est sans étoile.

Marcel-Paul Schützenberger a donné la caractérisation suivante des langages sans étoile : Modèle:Théorème On trouvera une démonstration de ce théorème dans les ouvrages francophonesModèle:,Modèle:,. Ce résultat est le point de départ de la théorie des variétés des langages formels.

Un exemple d'application de cette caractérisation est une preuve que le langage $L=(aa{)}^{*}$ n'est pas un langage sans étoile. Le monoïde syntaxique de ce langage est isomorphe à $\mathbb{Z}/2\mathbb{Z}$ ; ce groupe n'étant pas trivial, le monoïde syntaxique de $L$ n'est pas apériodique, donc $L$ n'est pas, d'après le théorème de Schützenberger, un langage sans étoile.

Automates sans compteurs

Les langages sans étoile sont également les langages acceptés par certains automates finis, appelés les automates sans compteurs. Un automate fini déterministe complet $A=(Q,\mathrm{\Sigma },I,\delta ,F)$ est sans compteur si, pour tout mot $w\in {\mathrm{\Sigma }}^{*}$, pour tout état $p\in Q$, et pour tout entier naturel $m\ge 1$,

$\delta (p,w^m)=p$ implique $\delta (p,w)=p$.

Le théorème énoncé par Robert McNaughton et Seymour Papert en 1971 formule cette caractérisation :

Autres caractérisations

Les langages sans étoile possèdent d'autres caractérisations :

• Ce sont les langages définissables dans la logique du premier ordre sur des ensembles linéairement ordonnés, notée FO[<] ;
• Ce sont les langages reconnus par les automates « très faiblement alternants », une forme affaiblie des automates finis alternants ;Modèle:Référence nécessaire
• Ce sont enfin les langages définissables en logique temporelle linéaire.

Les langages sans étoile appartiennent tous à la classe de complexité AC⁰ qui est une des premières classes considérées en complexité descriptive.

Ces équivalences restent valables, mutatis mutandis, pour des ensembles de mots infinis.

Exemple

Reprenons l'exemple présenté en introduction : le langage $L$ des mots ne comportant pas deux a consécutifs sur l'alphabet $\mathrm{\Sigma }=\{a,b\}$ :

• Une expression rationnelle de hauteur d'étoile 2 qui le dénote est par exemple $(b^{*}+a\cdot b{)}^{*}+(b^{*}+a\cdot b{)}^{*}\cdot a$.
• Une expression rationnelle sans étoile qui le dénote est $({\mathrm{\varnothing }}^{c}aa{\mathrm{\varnothing }}^c{)}^c$.
• Son monoïde syntaxique est $M(L)=\{\overline{ϵ},\bar{a},\bar{b},\overline{ab},\overline{ba}\}$.

$M(L)$ est bien un monoïde apériodique car il ne contient aucun groupe non trivial. Donc d'après la caractérisation de Schützenberger, il s'agit bien d'un langage sans étoile.

Bibliographie

• 1961 — Modèle:Ouvrage
• 1965 — Modèle:Article
• 1968 — Modèle:Ouvrage
• 1986 — Jean-Eric Pin, Variétés de langages formels, Éditions Masson, 1984 (version anglophone: Varieties of formal languages, Plenum Press, 1986).
• 2003 — Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, 2003 (version anglophone: Elements of automata theory, Cambridge University Press, 2009)
• 2008 — Modèle:Chapitre
• 2008 — Modèle:Carton2008
• 2021 — Modèle:Article

Articles connexes

• Hauteur d'étoile
• Monoïde syntaxique
• Relations de Green
• Langage local
• Théorème des variétés d'Eilenberg