Langage sans étoile

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En informatique théorique, et notamment en théorie des langages formels, un langage sans étoile (star-free language en anglais) est un langage rationnel particulier : un tel langage 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 .

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.

Avec cette définition 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 :  ; tous les langages finis sont également des langages sans étoile. Comme les langages rationnels généraux sont fermés par complémentations, on voit que les langages sans étoile sont un sous-ensemble des langages rationnels.

De manière équivalente, les langages sans étoile sont ceux qui admettent une expression rationnelle pouvant contenir des constructions pour le complémentaire mais pas d'étoile.

Autres exemples et contre-exemples[modifier | modifier le code]

  • Comme déjà dit plus haut, le langage est sans étoile;
  • L'ensemble {ε} réduit au mot vide est sans étoile : c'est le complément de
  • Sur , le langage est sans étoile[1]
  • Tout langage local est sans étoile.
  • Le langage 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 n'est pas un langage sans étoile. Le monoïde syntaxique de ce langage est isomorphe à  ; ce groupe n'étant pas trivial, le monoïde syntaxique de n'est pas apériodique, donc 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 est sans compteur si, pour tout mot , pour tout état , et pour tout entier naturel ,

implique .

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] :

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 des mots ne comportant pas deux a consécutifs sur l'alphabet  :

  • Une expression rationnelle de hauteur d'étoile 2 qui le dénote est par exemple .
  • Une expression rationnelle sans étoile qui le dénote est .
  • Son monoïde syntaxique est .

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

  1. a, b et c Carton 2008, Section 1.12 : Langages sans étoile.
  2. Schützenberger 1965.
  3. Jean-Eric Pin, Variétés de langages formels, Paris, Masson,
  4. Jacques Sakarovitch, Éléments de théorie des automates, Vuibert,
  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).
  8. Diekert et Gastin 2008.
  9. Kamp (1968).

Bibliographie[modifier | modifier le code]

  • (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, (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),
  • Olivier Carton, Langages formels, calculabilité et complexité, [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[modifier | modifier le code]