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 ${\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}$.

Monoïde syntaxique

É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}$.

Monoïde des transitions

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

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

${\displaystyle 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 ${\displaystyle \mu :A^{*}\rightarrow R_{Q}}$qui à un mot ${\displaystyle w}$ associe la relation définie par les couples d'états ${\displaystyle (q,q')}$ tels qu'il existe un chemin de q à q' étiqueté par w :

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

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

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

Théorèmes

Rationalité par morphisme

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.

Monoïde syntaxique et monoïde des transitions

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}$.

Exemples

Un exemple simple

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}$.

Un deuxième exemple

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.

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.

Références

• 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

• Portail de l'informatique théorique
• Portail de la logique
• Portail des mathématiques