Monoïde syntaxique

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

Reconnaissance par morphisme et par monoïde

Soit $L\subset A^{*}$ un langage sur un alphabet $A$, soit $M$ un monoïde et soit $\mu$ un morphisme de $A^{*}$ dans $M$. On dit que le morphisme $\mu$ reconnaît $L$ si et seulement si il existe une partie $P$ de $M$ telle que $\mu ^{-1}(P)=L$. On dit qu'un monoïde $M$ reconnaît $L$ s'il existe un morphisme $\mu :A^{*}\rightarrow M$ qui reconnaît $L$.

On a les résultats suivants :

• Si un monoïde $M$ reconnaît un langage $L$ et $M$ est un sous-monoïde de $M'$, alors $M'$reconnaît $L$.
• Si un monoïde $M$ reconnaît un langage $L$ et $M$ est quotient de $M'$, alors $M'$reconnaît $L$.
• Si un monoïde $M$ reconnaît un langage $L$ et $M$ divise $M'$ (c'est-à-dire que $M$ est un quotient d'un sous-monoïde de $M'$), alors $M'$reconnaît $L$.

Monoïde syntaxique

Étant donné un langage formel $L\subset A^{*}$ sur l'alphabet $A$, deux mots u et v sont dits syntaxiquement équivalents si tout mot w du langage dont u est un facteur donne un mot qui est encore dans le langage si on remplace l'occurrence de u par 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 de l'ensemble 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))$,

donc 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$ divise tout 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$.

Monoïde des transitions

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

Soit ${\mathcal {A}}=(Q,A,\delta ,i,T)$ un automate déterministe complet reconnaissant $L$. Ici $\delta$ est la fonction de transition. On note $R_{Q}$ l'ensemble des relations binaires sur $Q$ muni de la loi interne $\cdot$ définie par

 :\ (x,y)\in r_{1}\ {\text{et}}\ (y,z)\in r_{2}\}} $r_{1}\cdot r_{2}=\{(x,z)\in Q^{2}|\ \exists y\in Q\ :\ (x,y)\in r_{1}\ {\text{et}}\ (y,z)\in r_{2}\}$,

et on définit un morphisme $\mu :A^{*}\rightarrow R_{Q}$qui à un mot $w$ associe la relation définie par les couples d'états $(q,q')$ tels qu'il existe un chemin de q à q' étiqueté par w :

$w\rightarrow \{(q,q')\in Q^{2}|\ q\rightarrow ^{w}q'\}$.

En posant $P=\{r\in R_{Q}\mid \ r\cap (\{i\}\times T)\neq \varnothing \}$ on a bien $L=\mu ^{-1}(P)$. En d'autres termes, le monoïde $R_{Q}$ reconnaît $L$.

Ce monoïde est appelé le monoïde des transitions de l'automate. Le monoïde syntaxique du langage $L$ est isomorphe au monoïde des transitions de l'automate minimal reconnaissant $L$.

Théorèmes

Rationalité par morphisme

Un langage $L\ {\underline {\subset }}\ A^{*}$ est rationnel si et seulement s'il est reconnu par un monoïde fini. En particulier, comme le monoïde syntaxique divise tout monoïde reconnaissant $L$, le langage est rationnel si et seulement si son monoïde syntaxique est fini.

Démonstration

Soit $L{\underline {\subset }}A^{*}$ un langage reconnu par un monoïde fini. Il existe donc un monoïde $M$ et un morphisme $\mu :A^{*}\longrightarrow M$ tel qu'il existe une partie $P$ de $M$. On construit l'automate ${\mathcal {A}}=(M,A,E,\{1\},P)$ où l'ensemble de transitions est $E=\{(m,a,m\mu (a))|m\in M,a\in A\}$. Cet automate reconnaît $L$, ce qui prouve le sens indirect de l'assertion. Réciproquement si un langage $L$ est rationnel alors il est reconnu par un automate fini déterministe ${\mathcal {A}}=(Q,A,\delta ,i,T)$ , il suffit alors de prendre le monoïde des transitions qui reconnaît bien $L$ et qui est fini car $R_{Q}$ est l'ensemble des parties de $Q^{2}$ qui est fini car $Q$ est fini.

Monoïde syntaxique et monoïde des transitions

Le monoïde syntaxique $M(L)$ d'un langage rationnel $L$ est isomorphe au monoïde des transitions de l'automate minimal $L$.

Démonstration

D'après le théorème de rationalité par morphisme, le monoïde $M_{E}$ des transitions de l'automate minimal de $L$ reconnaît $L$. D'après un des résultats de la section "Reconnaissance par morphisme et par monoïde", $M_{E}$ est divisible par $M(L)$. Soient deux mots $w$ et $w'$ ayant des images différentes dans le monoïde des transitions de l'automate minimal. Puisque cet automate est déterministe, il existe un état $p$ tel que $p.w\neq p.w'$. Soient $q=p.w$, $q'=p.w'$. Puisque l'automate est minimal, il existe un mot $v$ tel que $q.v$ est final et $q.v'$ n'est pas final (quitte à considérer l'inverse). Il existe également un mot $u$ tel que $i.u=p$. On en déduit que $(u,v)$ appartient à $C(w)$ mais pas à $C(w')$ et que $w$ et $w'$ ont des images différentes dans le monoïde syntaxique.

Exemples

Un exemple simple

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

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

Un deuxième exemple

Automate reconnaissant le langage $a^{*}b^{*}$.

Soit $L=a^{*}b^{*}$ le langage reconnu par l’automate déterministe incomplet de la deuxième figure. Il y a cinq contextes :

• Les couples de la forme $(a^{n},a^{m}b^{k})$ avec $n\geq 0,m\geq 0,k\geq 0$ ou $(a^{n}b^{m},b^{k})$ avec $n\geq 0,m\geq 1,k\geq 0$. C'est le contexte de $\varepsilon$ ;
• Les couples de la forme $(a^{n},a^{m}b^{k})$ avec $n\geq 0,m\geq 0,k\geq 0$. C'est le contexte des mots dans $a^{+}$ ;
• Les couples de la forme $(a^{n},b^{m})$ avec $n\geq 0,m\geq 0$. C'est le contexte des mots de $a^{+}b^{+}$ ;
• Les couples de la forme $(b^{n},b^{m})$ avec $n\geq 0,m\geq 0$. C'est le contexte des mots de $b^{+}$ ;
• Les autres couples. C'est le contexte des mots qui ne sont pas dans $L$. Le langage $L$ est union des quatre premières classes d'équivalence.

Le monoïde syntaxique a cinq éléments, images de l'un des mots de chaque classe, par exemple de $\varepsilon$, de $a$, de $ab$, 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 le mot vide $\varepsilon$, par les lettres $a$ et $b$ et par les mots $ab$ et $ba$ sont indiquées dans la table suivante.

	$\varepsilon$	a	b	ab	ba
1	1	1	2	2	3
2	2	3	2	3	3
3	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 {\varepsilon }}$ 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.

Un autre exemple

On peut aussi montrer que le monoïde syntaxique du langage de Dyck sur une paire de parenthèses est le monoïde bicyclique.

Bibliographie

• Olivier Carton, Langages formels, calculabilité et complexité, 2008 [détail de l’édition] (lire en ligne)
• 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

• Théorème des variétés d'Eilenberg
• Langage sans étoile
• Monoïde apériodique
• Congruence de Simon