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 $\{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 $(\emptyset ^{c}aa\emptyset ^{c})^{c}$ , où $X^{c}$ dénote le complément d'une partie $X$ de $\{a,\,b\}^{*}$ .

Définition[modifier | modifier le code]

La famille des langages sans étoiles est^[1] 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[modifier | modifier le code]

Les langages suivants sont sans étoile.

Le langage $\Sigma ^{*}$ contenant tous les mots sur un alphabet $\Sigma$ , parce qu'il est le complémentaire de l'ensemble vide : $\Sigma ^{*}=\emptyset ^{c}$ ;
L'ensemble {ε} réduit au mot vide est sans étoile : c'est le complément de $\Sigma ^{*}\Sigma$ ;
tous les langages finis sont également des langages sans étoile.
Sur $\Sigma =\{a,b\}$ , le langage $(ab)^{+}=(a\Sigma ^{*}\cap \Sigma ^{*}b)\setminus \Sigma ^{*}(aa+bb)\Sigma ^{*}$ est sans étoile^[1]
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[modifier | modifier le code]

Théorème de Schützenberger[modifier | modifier le code]

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^[2] suivante des langages sans étoile :

Théorème — Les langages sans étoile sont les langages dont le monoïde syntaxique est fini et apériodique.

On trouvera une démonstration de ce théorème dans les ouvrages francophones^[3]^,^[4]^,^[1]. 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[modifier | modifier le code]

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,\Sigma ,I,\delta ,F)$ est sans compteur si, pour tout mot $w\in \Sigma ^{*}$ , pour tout état $p\in Q$ , et pour tout entier naturel $m\geq 1$ ,

\delta (p,w^{m})=p\quad

implique

\quad \delta (p,w)=p

.

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

McNaughton et Papert — Un langage est sans étoile si et seulement si son automate minimal est fini et sans compteur.

Autres caractérisations[modifier | modifier le code]

Les langages sans étoile possèdent d'autres caractérisations^[7] :

Ce sont les langages définissables dans la logique du premier ordre sur des ensembles linéairement ordonnés, notée FO[<]^[8] ;
Ce sont les langages reconnus par les automates « très faiblement alternants », une forme affaiblie des automates finis alternants ;
Ce sont enfin les langages définissables en logique temporelle linéaire^[9].

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[modifier | modifier le code]

Reprenons l'exemple présenté en introduction : le langage $L$ des mots ne comportant pas deux a consécutifs sur l'alphabet $\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 $(\emptyset ^{c}aa\emptyset ^{c})^{c}$ .
Son monoïde syntaxique est $M(L)=\{{\overline {\epsilon }},{\overline {a}},{\overline {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.

Références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Star-free language » (voir la liste des auteurs).

↑ ^{a b et c} Carton 2008, Section 1.12 : Langages sans étoile.
↑ Schützenberger 1965.
↑ Jean-Eric Pin, Variétés de langages formels, Paris, Masson, 1984
↑ Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, 2003
↑ McNaughton et Papert 1971.
↑ « Langage formels - Langages08.pdf »
↑ Une présentation de ces équivalences, et de la preuve de ces équivalences, est donnée dans Diekert et Gastin (2008).
↑ Diekert et Gastin 2008.
↑ Kamp (1968).

Bibliographie[modifier | modifier le code]

1961 — Robert McNaughton et Seymour Papert, Counter-free Automata, Cambridge, MIT Press, 1971, 163 p. (ISBN 978-0-262-13076-9, LCCN 71153294)
1965 — Marcel-Paul Schützenberger, « On finite monoids having only trivial subgroups », Information and Control, vol. 8, n^o 2,‎ 1965, p. 190–194 (lire en ligne)
1968 — Johan A. W. Kamp, Tense Logic and the Theory of Linear Order, University of California at Los Angeles (UCLA), 1968
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 — Volker Diekert et Paul Gastin, « First-order definable languages », dans Jörg Flum, Erich Grädel et Thomas Wilke (éditeurs), Logic and automata: history and perspectives, Amsterdam University Press, 2008 (ISBN 9789053565766, lire en ligne), p. 261-306
2008 — Olivier Carton, Langages formels, calculabilité et complexité, 2008 [détail de l’édition] (lire en ligne)
2021 — Emmanuel Arrighi, Henning Fernau, Stefan Hoffmann et Markus Holzer, « On the Complexity of Intersection Non-emptiness for Star-Free Language Classes », Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, vol. 213 « 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021) »,‎ 2021, p. 34:1–34:15 (ISBN 978-3-95977-215-0, DOI 10.4230/LIPIcs.FSTTCS.2021.34, lire en ligne)

Articles connexes[modifier | modifier le code]

[Carton-1] {a b et c} Carton 2008, Section 1.12 : Langages sans étoile.

[Schutz-2] Schützenberger 1965.

[3] Jean-Eric Pin, Variétés de langages formels, Paris, Masson, 1984

[4] Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, 2003

[McNaughtonPapert-5] McNaughton et Papert 1971.

[6] « Langage formels - Langages08.pdf »

[7] Une présentation de ces équivalences, et de la preuve de ces équivalences, est donnée dans Diekert et Gastin (2008).

[DiekertGastin-8] Diekert et Gastin 2008.

[Kamp-9] Kamp (1968).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

v · m Automates finis et langages réguliers
Articles généraux	Théorie des automates Automate fini Machine abstraite
Automates finis	Automate fini déterministe Automate fini inambigu Automate fini non déterministe Construction par sous-ensembles Automate sur les mots infinis
Automates finis particuliers	Automate alternant Automate bidirectionnel Automate pondéré Automate probabiliste Automate quantique Automate temporisé Automate de Büchi Automate de Muller Modèle de Markov caché Système de transition d'états Structure de Kripke Machine à états abstraits Machine de Mealy Machine de Moore Transducteur fini Automate séquentiel
Langages réguliers	Langage rationnel Langage sans étoile Langage local Langage congruentiel Langage stochastique Lemme de l'étoile Lemme d'Arden ω-langage rationnel
Des automates aux langages	Expression régulière Algorithme de Conway Algorithme de McNaughton et Yamada Méthode de Brzozowski et McCluskey
Des langages aux automates	Dérivée de Brzozowski Algorithme de Thompson Construction de Glushkov Complexité en états
Minimisation	Théorème de Myhill-Nerode Équivalence de Nerode Minimisation d'un automate fini déterministe Algorithme de Moore Algorithme de Brzozowski Algorithme de Hopcroft
Équivalences	Théorème de Kleene Étoile de Kleene Monoïde syntaxique Théorème des variétés d'Eilenberg