Monoïde syntaxique

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

On a les résultats suivants :

• Si un monoïde ${\displaystyle M}$ reconnaît un langage ${\displaystyle L}$ et ${\displaystyle M}$ est un sous monoïde de ${\displaystyle M'}$, alors ${\displaystyle M'}$reconnaît ${\displaystyle L}$.
• Si un monoïde ${\displaystyle M}$ reconnaît un langage ${\displaystyle L}$ et ${\displaystyle M}$ est quotient de ${\displaystyle M'}$, alors ${\displaystyle M'}$reconnaît ${\displaystyle L}$.
• Si un monoïde ${\displaystyle M}$ reconnaît un langage ${\displaystyle L}$ et ${\displaystyle M}$ divise ${\displaystyle M'}$, alors ${\displaystyle M'}$reconnaît ${\displaystyle L}$.

Étant donné un langage formel ${\displaystyle L\subset A^{*}}$ sur l'alphabet ${\displaystyle 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 ${\displaystyle u}$ est l'ensemble ${\displaystyle C(u)}$ des couples de mots ${\displaystyle (x,y)}$ tels que ${\displaystyle xuy\in L}$. Deux mots u et v sont syntaxiquement équivalents s'ils ont même contexte, soit

${\displaystyle 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 ${\displaystyle A^{*}}$ par la relation ${\displaystyle \sim }$ est un monoïde, appelé le monoïde syntaxique de ${\displaystyle L}$. Le morphisme de ${\displaystyle A^{*}}$ sur ce monoïde qui à un mot associe sa classe est le morphisme syntaxique.

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

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

${\displaystyle L=f^{-1}(P)=f^{-1}(f(L))}$,

donc le monoïde syntaxique reconnaît ${\displaystyle L}$.

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

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

Un langage ${\displaystyle 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 ${\displaystyle L}$, le langage est rationnel si et seulement si son monoïde syntaxique est fini.

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

Automate reconnaissant les mots contenant un nombre impair de lettres ${\displaystyle a}$.

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

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

Soit ${\displaystyle 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 ${\displaystyle (a^{n},a^{m}b^{k})}$ avec ${\displaystyle n\geq 0,m\geq 0,k\geq 0}$ ou ${\displaystyle (a^{n}b^{m},b^{k})}$ avec ${\displaystyle n\geq 0,m\geq 1,k\geq 0}$. C'est le contexte de ${\displaystyle \varepsilon }$ ;
• Les couples de la forme ${\displaystyle (a^{n},a^{m}b^{k})}$ avec ${\displaystyle n\geq 0,m\geq 0,k\geq 0}$. C'est le contexte des mots dans ${\displaystyle a^{+}}$ ;
• Les couples de la forme ${\displaystyle (a^{n},b^{m})}$ avec ${\displaystyle n\geq 0,m\geq 0}$. C'est le contexte des mots de ${\displaystyle a^{+}b^{+}}$ ;
• Les couples de la forme ${\displaystyle (b^{n},b^{m})}$ avec ${\displaystyle n\geq 0,m\geq 0}$. C'est le contexte des mots de ${\displaystyle b^{+}}$ ;
• Les autres couples. C'est le contexte des mots qui ne sont pas dans ${\displaystyle L}$. Le langage ${\displaystyle 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 ${\displaystyle \varepsilon }$, de ${\displaystyle a}$, de ${\displaystyle ab}$, de ${\displaystyle b}$ et de ${\displaystyle 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 ${\displaystyle 3}$. Les fonctions définies par le mot vide ${\displaystyle \varepsilon }$, par les lettres ${\displaystyle a}$ et ${\displaystyle b}$ et par les mots ${\displaystyle ab}$ et ${\displaystyle ba}$ sont indiquées dans la table suivante.

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

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