Monoïde syntaxique

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

En informatique théorique, et en particulier dans la théorie des automates finis, le monoïde syntaxique d'un langage formel est un monoïde naturellement attaché au langage.

L'étude de ce monoïde permet de refléter certaines propriétés combinatoires du langage par des caractéristiques algébriques du monoïde. L'exemple le plus célèbre de cette relation est la caractérisation, due à Marcel-Paul Schützenberger, des langages rationnels sans étoile (que l'on peut décrire par des expressions rationnelles avec complément mais sans l'étoile de Kleene): ce sont les langages dont le monoïde syntaxique est fini et apériodique, c'est-à-dire ne contient pas de sous-groupe non trivial.

Définition[modifier | modifier le code]

Étant donné un langage formel L\subset A^* sur l'alphabet A, on dit que deux mots u et v sont syntaxiquement équivalents si tout mot du langage dont u est un facteur définit un mot du langage dont v est un facteur en remplaçant l'occurrence de u par celle de v. Formellement, le contexte d'un mot u est l'ensemble C(u) des couples de mots (x,y) tels que xuy\in L. Deux mots u et v sont syntaxiquement équivalents s'ils ont même contexte, soit

u\sim v \iff C(u)=C(v)\iff\forall x,y\in A^*,  \left( x\, u\, y \in L \iff x\, v\, y \in L\right).

Cette équivalence est en fait une congruence de monoïde, c'est-à-dire compatible à gauche et à droite avec la multiplication. Le quotient des mots A^* par la relation \sim est un monoïde, appelé le monoïde syntaxique de L. Le morphisme de A^* sur ce monoïde qui à un mot associe sa classe est le morphisme syntaxique.

Le langage L est saturé pour la congruence syntaxique, c'est-à-dire qu'il est union de classes de la congruence syntaxique. En effet, si u est un mot de L, alors le couple (\varepsilon,\varepsilon) appartient au contexte de u, donc de tout mot v équivalent à u, ce qui implique que v est dans L et donc que la classe de u est contenue dans L.

Soit f le morphisme canonique de A^* sur le monoïde syntaxique de L, et soit P=f(L) l'image de L dans ce monoïde. Alors on a

L=f^{-1}(P)=f^{-1}(f(L)).

On dit que le monoïde syntaxique reconnaît L.

Les propriétés sont extrémales au sens suivant.

  • La congruence syntaxique de L est la plus grossière des congruences sur A^* qui sature L.
  • Le monoïde syntaxique de L est le plus petit monoïde qui reconnaît L: pour tout monoïde M qui reconnaît L, il existe un morphisme surjectif de M sur le monoïde syntaxique de L.

Une autre définition[modifier | modifier le code]

Une définition équivalente, et qui se prête mieux aux calculs, est la suivante.

Soit {\mathcal A}= (Q, i, T) un automate déterministe complet reconnaissant L. Chaque mot w définit une application \bar w:Q\to Q par (q)w=q\cdot w (notation à droite, pour obtenir un morphisme). Le monoïde de transition de cet automate est le monoïde des applications \bar w, pour tous les mots de A^*. Le monoïde syntaxique du langage L est isomorphe au monoïde de transition de l'automate minimal reconnaissant L.

Exemples[modifier | modifier le code]

Un exemple simple[modifier | modifier le code]

Automate reconnaissant les mots contenant un nombre impair de lettres a.

Le monoïde de transition de cet automate a deux éléments: l'identité sur \{1,2\} et la permutation (1 2) qui échange 1 et 2. Les mots contenant un nombre pair de lettres a ont pour image l'identité, les autres la permutation (1 2). Le monoïde syntaxique est le groupe des entiers modulo 2.

Un deuxième exemple[modifier | modifier le code]

Automate reconnaissant le langage a^*b^*

Soit L=a^*b^* le langage reconnu par l’automate déterministe incomplet de la figure. Il y a contextes:

  • Les couples de la forme (a^n,a^m) avec n\ge0, m\ge1. C'est le contexte des mots dans a^*.
  • Les couples de la forme (a^n,a^mb^k) avec n\ge0, m\ge0, k>1. C'est le contexte des mots de a^*b^+.
  • Les autres couples. C'est le contexte des mots qui ne sont pas dans L. Le langage L est union des deux premières classes d'équivalence.

Le monoïde syntaxique a trois éléments, images de l'un des mots de chaque classe, par exemple de a, de b et de ba respectivement.

Pour calculer le monoïde de transition, on complète d'abord l'automate par un état puits numéroté par exemple par 3. Les fonctions définies par les lettres a et b et par le mot ba sont indiquées dans la table suivante.

a b ba
1 1 2 3
2 3 2 3
3 3 3 3

L'image \overline{ba} est un zéro du monoïde: son produit avec tout autre élément est égal à lui-même. L'image \overline{a} est l'élément neutre du monoïde. Enfin, l'image de \overline{b} est un idempotent (c'est-à-dire qu'il est égal à son carré) mais différent de l’élément neutre.

D'autres exemples[modifier | modifier le code]

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

  • Jean-Éric Pin, « Syntactic semigroups », dans G. Rozenberg, A. Salomaa (éditeurs), Handbook of Formal Languages, vol. 1 : Word, Language, Grammar, Springer Verlag,‎ 1997 (ISBN 978-3540604204), p. 679-746

Articles connexes[modifier | modifier le code]