Monoïde syntaxique - Syntactic monoid

En mathématiques et en informatique , le monoïde syntaxique d'un langage formel est le plus petit monoïde qui reconnaît le langage . ${\style d'affichage M(L)}$ ${\style d'affichage L}$${\style d'affichage L}$

Quotient syntaxique

Le monoïde libre sur un ensemble donné est le monoïde dont les éléments sont toutes les chaînes de zéro ou plusieurs éléments de cet ensemble, avec la concaténation de chaînes comme opération monoïde et la chaîne vide comme élément d'identité . Étant donné un sous - ensemble d'un monoïde libre , on peut définir des ensembles constitués d' inverses formels à gauche ou à droite d'éléments dans . Ceux-ci sont appelés quotients , et on peut définir des quotients à droite ou à gauche, selon le côté que l'on concatène. Ainsi, le quotient droit de par un élément de est l'ensemble ${\style d'affichage S}$${\style d'affichage M}$${\style d'affichage S}$${\style d'affichage S}$${\style d'affichage m}$${\style d'affichage M}$

${\displaystyle S\ /\ m=\{u\in M\;\vert \;um\in S\}.}$

De même, le quotient de gauche est

${\displaystyle m\setminus S=\{u\in M\;\vert \;mu\in S\}.}$

Équivalence syntaxique

Le quotient syntaxique induit une relation d'équivalence sur , appelée relation syntaxique , ou équivalence syntaxique (induite par ). ${\style d'affichage M}$${\style d'affichage S}$

La bonne équivalence syntaxique est la relation d'équivalence

${\displaystyle s\sim _{S}t\ \Leftrightarrow \ S\,/\,s\;=\;S\,/\,t\ \Leftrightarrow \ (\forall x\in M\colon \ xs\ dans S\Leftrightarrow xt\dans S)}$.

De même, l' équivalence syntaxique de gauche est

${\displaystyle s\;{}_{S}{\sim }\;t\ \Leftrightarrow \ s\setminus S\;=\;t\setminus S\ \Leftrightarrow \ (\forall y\in M\colon \ sy\in S\Leftrightarrow ty\in S)}$.

Observez que l' équivalence syntaxique droite est une congruence gauche par rapport à la concaténation de chaînes et vice versa ; c'est-à-dire pour tous . ${\displaystyle s\sim _{S}t\ \Rightarrow \ xs\sim _{S}xt\ }$${\style d'affichage x\en M}$

La congruence syntaxique ou Myhill congruence est définie comme

${\displaystyle s\equiv _{S}t\ \Leftrightarrow \ (\forall x,y\in M\colon \ xsy\in S\Leftrightarrow xty\in S)}$.

La définition s'étend à une congruence définie par un sous-ensemble d'un monoïde général . Un ensemble disjonctif est un sous-ensemble tel que la congruence syntaxique définie par est la relation d'égalité. ${\style d'affichage S}$${\style d'affichage M}$${\style d'affichage S}$${\style d'affichage S}$

Appelons la classe d'équivalence de pour la congruence syntaxique. La congruence syntaxique est compatible avec la concaténation dans le monoïde, en ce que l'on a ${\style d'affichage [s]_{S}}$${\style d'affichage s}$

${\displaystyle [s]_{S}[t]_{S}=[st]_{S}}$

pour tous . Ainsi, le quotient syntaxique est un morphisme monoïde , et induit un quotient monoïde${\displaystyle s,t\in M}$

${\displaystyle M(S)=M\ /\ {\equiv _{S}}}$.

Ce monoïde est appelé le monoïde syntaxique de . On peut montrer que c'est le plus petit monoïde qui reconnaît ; c'est-à-dire, reconnaît , et pour chaque monoïde reconnaissant , est un quotient d'un sous- monoïde de . Le monoïde syntaxique de est aussi le monoïde de transition de l' automate minimal de . ${\style d'affichage M(S)}$${\style d'affichage S}$ ${\style d'affichage S}$${\style d'affichage M(S)}$${\style d'affichage S}$${\style d'affichage N}$${\style d'affichage S}$${\style d'affichage M(S)}$${\style d'affichage N}$${\style d'affichage S}$${\style d'affichage S}$

Une langue de groupe est une langue pour laquelle le monoïde syntaxique est un groupe .

Théorème de Myhill-Nerode

Le théorème de Myhill-Nerode déclare : une langue est régulière si et seulement si la famille de quotients est finie, ou de manière équivalente, l'équivalence syntaxique gauche a un indice fini (ce qui signifie qu'elle se divise en un nombre fini de classes d'équivalence). ${\style d'affichage L}$${\displaystyle \{m\setminus L\,\vert \;m\in M\}}$${\displaystyle {}_{S}{\sim }}$${\style d'affichage M}$

Ce théorème a été prouvé pour la première fois par Anil Nerode ( Nerode 1958 ) et la relation est donc appelée congruence de Nerode par certains auteurs. ${\displaystyle {}_{S}{\sim }}$

Preuve

La preuve de la partie "seulement si" est la suivante. Supposons qu'un automate fini reconnaissant lit l'entrée qui conduit à l'état . Si est une autre chaîne lue par la machine, se terminant également dans le même état , alors clairement on a . Ainsi, le nombre d'éléments dans est au plus égal au nombre d'états de l'automate et est au plus au nombre d'états finaux. ${\style d'affichage L}$${\style d'affichage x}$${\style d'affichage p}$${\style d'affichage y}$${\style d'affichage p}$${\displaystyle x\setminus L\,=y\setminus L}$${\displaystyle \{m\setminus L\,\vert \;m\in M\}}$${\displaystyle \{m\setminus L\,\vert \;m\in L\}}$

Pour une preuve de la partie "si", supposons que le nombre d'éléments dans est fini. On peut alors construire un automate où est l'ensemble des états, est l'ensemble des états finaux, le langage est l'état initial, et la fonction de transition est donnée par . Clairement, cet automate reconnaît . Ainsi, un langage est reconnaissable si et seulement si l'ensemble est fini. Notez que cette preuve construit aussi l'automate minimal. ${\displaystyle \{m\setminus L\,\vert \;m\in M\}}$${\displaystyle Q=\{m\setminus L\,\vert \;m\in M\}}$${\displaystyle F=\{m\setminus L\,\vert \;m\in L\}}$${\style d'affichage L}$${\displaystyle y\setminus (x\setminus L)=(xy)\setminus L}$${\style d'affichage L}$${\style d'affichage L}$${\displaystyle \{m\setminus L\,\vert \;m\in M\}}$

Exemples

• Soit la langue sur des mots de même longueur. La congruence syntaxique a deux classes, elle-même et , les mots de longueur impaire. Le monoïde syntaxique est le groupe d'ordre 2 sur .${\style d'affichage L}$${\style d'affichage A=\{a,b\}}$${\style d'affichage L}$${\style d'affichage L_{1}}$${\style d'affichage \{L,L_{1}\}}$
• Le monoïde bicyclique est le monoïde syntaxique du langage de Dyck (le langage des ensembles équilibrés de parenthèses).
• Le monoïde libre sur (où ) est le monoïde syntaxique de la langue , où est l'inversion du mot .${\style d'affichage A}$${\displaystyle \left|A\right|>1}$${\displaystyle \{ww^{R}\mid w\in A^{*}\}}$${\style d'affichage w^{R}}$${\style d'affichage w}$
• Tout monoïde fini est homomorphe au monoïde syntaxique d'un langage non trivial, mais tout monoïde fini n'est pas isomorphe à un monoïde syntaxique.
• Chaque groupe fini est isomorphe au monoïde syntaxique d'un langage non trivial.
• Le langage sur lequel le nombre d'occurrences de et sont congrus modulo est un langage de groupe à monoïde syntaxique .${\style d'affichage \{a,b\}}$${\style d'affichage a}$${\style d'affichage b}$${\style d'affichage 2^{n}}$${\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} }$
• Les monoïdes traces sont des exemples de monoïdes syntaxiques.
• Marcel-Paul Schützenberger a caractérisé les langues sans étoiles comme celles avec des monoïdes syntaxiques apériodiques finis.

Les références

• Anderson, James A. (2006). Théorie des automates avec applications modernes . Avec des contributions de Tom Head. Cambridge : Cambridge University Press . ISBN 0-521-61324-8. Zbl  1127.68049 .
• Holcombe, WML (1982). Théorie des automates algébriques . Études de Cambridge en mathématiques avancées. 1 . Presse de l'Université de Cambridge . ISBN 0-521-60492-3. Zbl  0489.68046 .
• Lawson, Mark V. (2004). Automates finis . Chapman et Hall/CRC. ISBN 1-58488-255-7. Zbl  1086.68074 .
• Pin, Jean-Éric (1997). "10. Semi-groupes syntaxiques". Dans Rozenberg, G.; Salomaa, A. (éd.). Manuel de théorie du langage formel (PDF) . 1 . Springer-Verlag . p. 679-746. Zbl  0866.68057 .
• Sakarovitch, Jacques (2009). Éléments de théorie des automates . Traduit du français par Ruben Thomas. Presse de l'Université de Cambridge . ISBN 978-0-521-84425-3. Zbl  1188.68177 .
• Straubing, Howard (1994). Automates finis, logique formelle et complexité des circuits . Progrès en informatique théorique. Bâle : Birkhäuser. ISBN 3-7643-3719-2. Zbl  0816.68086 .