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]

Reconnaissance par morphisme et par monoïde[modifier | modifier le code]

Soit un langage sur un alphabet , un monoïde et un morphisme de dans . On dit que le morphisme reconnait si et seulement si il existe une partie de telle que .

On dit qu'un monoïde reconnait s'il existe un morphisme tels que reconnait .

On a de plus les résultats suivants :

  • Si un monoïde reconnait un langage et est un sous monoïde de , alors reconnait .
  • Si un monoïde reconnait un langage et est quotient de , alors reconnait .
  • Si un monoïde reconnait un langage et divise , alors reconnait .

Monoïde Syntaxique[modifier | modifier le code]

Étant donné un langage formel sur l'alphabet , 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 est l'ensemble des couples de mots tels que . Deux mots u et v sont syntaxiquement équivalents s'ils ont même contexte, soit

.

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 par la relation est un monoïde, appelé le monoïde syntaxique de . Le morphisme de sur ce monoïde qui à un mot associe sa classe est le morphisme syntaxique.

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

Soit le morphisme canonique de sur le monoïde syntaxique de , et soit l'image de dans ce monoïde. Alors on a

.

Donc le monoïde syntaxique reconnaît .

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

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

Monoïde des transitions[modifier | modifier le code]

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

Soit un automate déterministe complet reconnaissant .

On pose l'ensemble des relations binaires sur muni de la loi interne telle que .

Et on définit le morphisme

En posant on a bien . D'où reconnait .

Ce monoïde est appelé monoïde des transitions.

De plus le monoïde syntaxique du langage est isomorphe au monoïde des transitions de l'automate minimal reconnaissant .

Théorèmes[modifier | modifier le code]

Rationalité par morphisme[modifier | modifier le code]

Un langage 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 , le langage est rationnel si et seulement si son monoïde syntaxique est fini

Monoïde syntaxique et monoïde des transitions[modifier | modifier le code]

Le monoïde syntaxique d'un langage rationnel est isomorphe au monoïde des transitions de l'automate minimal .

Exemples[modifier | modifier le code]

Un exemple simple[modifier | modifier le code]

Automate reconnaissant les mots contenant un nombre impair de lettres .

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

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

Automate reconnaissant le langage .

Soit le langage reconnu par l’automate déterministe incomplet de la figure. Il y a cinq contextes :

Les couples de la forme avec ou avec . C'est le contexte de  ;

  • Les couples de la forme avec . C'est le contexte des mots dans  ;
  • Les couples de la forme avec . C'est le contexte des mots de  ;
  • Les couples de la forme avec . C'est le contexte des mots de  ;
  • Les autres couples. C'est le contexte des mots qui ne sont pas dans . Le langage 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 , de , de , de et de respectivement.

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

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

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

Un autre exemple[modifier | modifier le code]

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[modifier | modifier le code]

Articles connexes[modifier | modifier le code]