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

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

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

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[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

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

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

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

(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).

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

(en) 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

Johan A. W. Kamp, Tense Logic and the Theory of Linear Order, University of California at Los Angeles (UCLA), 1968

(en) Robert McNaughton et Seymour Papert, Counter-free Automata, Cambridge, MIT Press, 1971, 163 p. (ISBN 978-0-262-13076-9, LCCN 71153294)

(en) 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)

Olivier Carton, Langages formels, calculabilité et complexité, 2008 [détail de l’édition] (lire en ligne)
Jean-Eric Pin, Variétés de langages formels, Éditions Masson, 1984 (version anglophone: Varieties of formal languages, Plenum Press, 1986).
Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, 2003 (version anglophone: Elements of automata theory, Cambridge University Press, 2009)

Articles connexes

Portail de la logique
Portail de l'informatique théorique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[Carton-1] 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).