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. Soit un langage sur un alphabet , soit un monoïde et soit un morphisme de dans . On dit que le morphisme reconnaît si et seulement si il existe une partie de telle que . On dit qu'un monoïde reconnaît s'il existe un morphisme qui reconnaît . On a les résultats suivants : Si un monoïde reconnaît un langage et est un sous monoïde de , alors reconnaît . Si un monoïde reconnaît un langage et est quotient de , alors reconnaît . Si un monoïde reconnaît un langage et divise , alors reconnaît . Étant donné un langage formel sur l'alphabet , 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 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.